Given a sequence $a$ of length $n$, where each element is an integer in $[1, n]$.

Define $f(i, j)$ as the number of $x$ such that $i \le x < j$ and $a_x \neq a_{x+1}$.

There are $m$ operations:

1 l r x: Update all elements in the range $[l, r]$ to $x$.

2 l r x: Query the sum of $f(i, j)$ for all $l \le i < j \le r$ such that $a_i = a_j = x$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ space-separated integers representing the sequence $a$.

The following $m$ lines each contain four space-separated integers $opt, l, r, x$ representing an operation.

Output

For each type $2$ operation, output one integer per line representing the answer.

Examples

Input 1

10 10
2 1 2 1 8 3 2 1 2 2
2 6 9 2
2 3 10 2
2 2 10 2
2 1 3 2
2 4 10 1
1 2 4 2
2 3 10 2
2 2 7 1
2 2 7 2
2 3 6 2

Output 1

2
20
20
2
4
30
0
9
0

Subtasks

Idea: nzhtl1477, Solution: nzhtl1477, Code: ccz181078, Data: ccz181078

For $20\%$ of the data, $1 \le n, m \le 1000$.

For another $20\%$ of the data, there are no type $1$ operations.

For another $10\%$ of the data, the operation types are in $[1, 2]$, $a_i$ and $x$ are generated uniformly at random in $[1, 100]$, and the endpoints $l, r$ of the range are generated uniformly at random in $[1, n]$ (if $l > r$, they are swapped).

For another $30\%$ of the data, $1 \le n, m \le 10^5$.

For $100\%$ of the data, $1 \le n, m \le 5 \times 10^5$, $1 \le l \le r \le n$, $1 \le a_i, x \le n$, and all inputs are integers.