Maintain a sequence $a_i$ of length $n$, with $m$ operations.

1. Modify the values in the range $[l, r]$ to $x$.
2. Query the number of distinct values in the range $[l, r]$, meaning that if the same number appears multiple times, it is counted only once.

Input

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

The second line contains $n$ integers representing $a_i$.

Each of the following $m$ lines is either $1\ l\ r\ x$ or $2\ l\ r$, representing a modification or a query, respectively.

Output

For each query, output a single number representing the answer.

Examples

Input 1

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

Output 1

5
3
1
1

Subtasks

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

$1\leq n, m \leq 10^5$, $1\leq a_i\leq 10^9$.