Given a sequence of integers $a_1, \dots, a_n$, perform $m$ operations.

Each operation provides $l, r, x$. First, perform a modification, then query how many distinct values are present in $a_1, \dots, a_x$.

If $l \le r$, the modification is to sort $a_l, \dots, a_r$ in non-decreasing order. Otherwise, the modification is to sort $a_r, \dots, a_l$ in non-increasing order.

Input

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

The second line contains $n$ integers $a_1, \dots, a_n$.

The next $m$ lines each contain three integers $l \oplus c, r \oplus c, x \oplus c$, representing each operation, where $\oplus$ is the bitwise XOR operator and $c$ is the answer to the query from the previous operation (specifically, for the first operation, $c=0$).

Output

Output $m$ lines, each containing an integer representing the answer to the query for each operation.

Examples

Input 1

9 7
2 2 8 8 2 8 2 1 3
2 2 2
3 7 6
6 7 1
9 6 7
10 11 10
7 0 5
5 1 7

Output 1

1
2
1
2
3
2
2

Subtasks

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

For $20\%$ of the data, $n, m \le 10^3$.

For another $20\%$ of the data, $a_i \le 10$.

For another $20\%$ of the data, $a_i \le 100$.

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

For $100\%$ of the data, $1 \le a_i \le n$, $1 \le l, r, x \le n$, $1 \le n, m \le 10^6$.