길이가 N인 정수 수열 A_1, A_2, ..., A_N이 주어진다. 이때 다음 형태의 쿼리 M개가 주어질 때, 각 쿼리의 답을 구하는 프로그램을 작성하시오.

• a b c: 이 세 정수를 이용해 먼저 실제 쿼리인 i, j, k를 다음과 같이 계산해야 한다.
  • i = a ⊕ last_ans
  • j = b ⊕ last_ans
  • k = c ⊕ last_ans
  • 여기서 ⊕는 비트별 배타적 논리합(XOR) 연산이다.
  • last_ans는 가장 최근에 출력한 쿼리의 정답이며, 첫 번째 쿼리에서는 last_ans = 0이다.

위의 식대로 계산한 후, 만약 i가 j보다 크다면(i > j) 두 수의 값을 서로 바꾼다(swap). 이후 최종적으로 결정된 구간 A_i, A_{i+1}, ..., A_j 중에서 k보다 큰 원소의 개수를 출력한다.

입력

첫째 줄에 수열의 크기 N과 쿼리의 개수 M이 공백을 사이에 두고 주어진다. 둘째 줄에는 수열을 이루는 N개의 정수가 공백을 사이에 두고 주어진다. 셋째 줄부터 M개의 줄에는 각 쿼리를 암호화한 세 정수 a, b, c가 주어진다.

(단, 1 ≤ N, M ≤ 100,000, 수열의 원소는 -1,000,000,000 이상 1,000,000,000 이하의 정수이다. 복호화 및 스왑 과정을 거친 후의 i, j는 항상 1 ≤ i ≤ j ≤ N을 만족하도록 입력이 보장된다.)

출력

각 쿼리마다 정답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

7 3
5 1 2 3 4 5 7
2 6 3
1 5 3
5 6 1

예제 출력 1

2
5
1