Given an array $a$ and $n$ sets, initially the $i$-th set contains only one element $i$, where each element in a set corresponds to an index in the array.

Define the number of identical values for an element $i$ in a set $S$, denoted as $F(S, i)$, as the number of elements $j \in S$ such that $a[i] = a[j]$.

Define the $k$-weight of a set $S$ as: the number of pairs $(i, j)$ such that $\forall i \in S, \forall j \in S$, $F(S, i) + F(S, j) \le k$. Here, $i=j$ is allowed, and $(i, j)$ and $(j, i)$ are considered distinct pairs.

Perform $m$ operations of two types:

1 x y: Move all elements from set $y$ into set $x$, then clear set $y$. It is guaranteed that sets $x$ and $y$ are non-empty before the operation.

2 x l r k: Query the $k$-weight of the elements in set $x$ that are within the range $[l, r]$. The query is independent and does not modify the sets.

Input

The first line contains two space-separated integers $n$ and $m$.

The second line contains $n$ integers representing the array.

The following $m$ lines each describe an operation in the format specified above.

Output

For each type 2 operation, output a single integer on a new line representing the answer to the query.

Examples

Input 1

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

Output 1

1
0
0
1
0
1
0
1
1
0
0
0
0
1
0
1
0
9
4
0
0

Subtasks

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

For $10\%$ of the data, $n, m \le 100$.

For another $20\%$ of the data, $n, m \le 10000$.

For another $20\%$ of the data, the query $k$ remains constant.

For $100\%$ of the data, $n \le 10^5$, $m \le 2 \times 10^5$, $0 \le a_i, k \le m$, $1 \le l \le r \le n$, $1 \le x, y \le n$.