구간 안의 작은 수

길이가 $N$인 수열 $A$가 있다. $Q$개의 쿼리를 순서대로 처리하라.

처음에 $ans=0$이다. 각 쿼리마다 세 정수 $a$, $b$, $c$가 주어지며 다음과 같이 $l$, $r$, $x$를 정한다.

• $l=((a \oplus ans) \bmod N)+1$
• $r=((b \oplus ans) \bmod N)+1$
• $x=c \oplus ans$

만약 $l>r$이면 두 값을 바꾼다. 각 쿼리마다 구간 $A_l,A_{l+1},\ldots,A_r$에서 $x$ 이하인 원소의 개수를 출력하고 출력한 값이 다음 쿼리의 $ans$가 된다.

첫 번째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 200\,000)$

두 번째 줄에 수열의 원소 $A_1,A_2,\ldots,A_N$이 주어진다. $(0 \leq A_i < 2^{30})$

세 번째 줄부터 $Q$개의 줄에 걸쳐 세 정수 $a$, $b$, $c$가 주어진다. $(0 \leq a,b,c < 2^{30})$

각 쿼리마다 구간에서 $x$ 이하인 원소의 개수를 한 줄에 하나씩 출력한다.