During his training before BJOI, EI heard about set block decomposition problems. He was very weak (and still is), and his algorithm was slower than others by a factor of $\log$. The only solution he could think of was to modify the block size to wrap the complexity into $\Theta(n \sqrt{n\log n})$. However, after seeing a modified version of the problem, he no longer knew how to solve it:

There are $n$ sets $S_i$, initially empty. There are $q$ operations to perform:

1. Insert an element $x$ into the $l$-th through $r$-th sets, i.e., for $l \le i \le r$, $S_i \leftarrow S_i \cup \{x\}$.
2. Query the size of the intersection of the $l$-th through $r$-th sets, i.e., $$\left| \bigcap_{i = l}^r S_i \right|$$

Input

The first line contains two integers $n, q$.

The next $q$ lines each start with an integer $op$ representing the operation type.

The corresponding inputs are 1 l r x or 2 l r.

Output

For each type 2 query, output an integer followed by a newline representing the answer.

Examples

Input 1

3 4
1 1 2 2
1 2 3 1
2 1 2
2 2 2

Output 1

1
2

Note 1

The sets after the operations are: $[\{2\},\{1,2\},\{1\}]$

Therefore, for the first query, $\{2\} \cap \{1, 2\} = \{2\}$.

Input 2

2 3
1 1 1 1
1 2 2 1
2 1 2

Output 2

1

Constraints

$1\le n, q \le 3 \times 10^5$, $1\le x \le q$, $1 \le l \le r \le n$

Subtask 1 (12 pts.): $1\le n, q \le 500$, number of inserted elements $|S| \le 10^5$

Subtask 2 (18 pts.): $1 \le n, q \le 5 \times 10^3$, number of inserted elements $|S| \le 10^5$

Subtask 3 (20 pts.): $1\le n, q \le 10^5$, number of inserted elements $|S| \le 10^5$

Subtask 4 (28 pts.): $1\le n, q \le 10^5$

Subtask 5 (22 pts.): $1 \le n, q \le 3 \times 10^5$

Subtask $+\infty$ (0 pts.): You need to calculate the sum of the answers for every sub-interval of the given interval.