给定整数序列 $a_1,\dots,a_n$ ，共 $m$ 次操作；

每次操作给出 $l,r,x$ ，首先进行修改，然后查询 $a_1,\dots,a_x$ 中有多少种不同的值。

若 $l\le r$ ，则进行的修改是将 $a_l,\dots,a_r$ 从小到大排序；否则进行的修改是将 $a_r,\dots,a_l$ 从大到小排序。

输入格式

第一行两个整数 $n,m$ ；

第二行 $n$ 个整数 $a_1,\dots,a_n$ ；

接下来 $m$ 行，每行三个整数 $l\oplus c,r\oplus c,x\oplus c$ ，依次表示每次操作，其中 $\oplus$ 是按位异或，$c$ 是上次操作的查询的答案（特别地，对于第一次操作，$c=0$）。

输出格式

共 $m$ 行，每行一个整数，依次表示每次操作的查询的答案。

样例数据

样例输入

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

样例输出

1
2
1
2
3
2
2

子任务

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $20\%$ 的数据，满足 $n,m\le 10^3$。

对于另外 $20\%$ 的数据，满足 $a_i\le 10$。

对于另外 $20\%$ 的数据，满足 $a_i\le 100$。

对于另外 $20\%$ 的数据，满足 $n,m\le 10^5$。

对于 $100\%$ 的数据，满足 $1\le a_i\le n$，$1\le l,r,x\le n$，$1\le n,m\le 10^6$。