Light Switching

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ lights, initially off. Support range toggles and range counts of lights that are on.

Input

The first line contains $n,m$. Each of the next $m$ lines is op l r.

• 0 l r: toggle every light from $l$ through $r$.
• 1 l r: count the lights that are on in that range.

Output

Print one line for every type 1 query.

Subtasks

• 20 points: $2\le n\le50$, $m\le50$.
• 30 points: $n,m\le5000$.
• 50 points: $2\le n\le10^5$, $1\le m\le10^5$, $1\le l\le r\le n$.

Examples

Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

Output

1
2

Explanation

After the first two toggles the state is 1 0 1 1, so range $[2,3]$ contains one on light. Toggling $[2,4]$ again gives 1 1 0 0, hence two lights are on.