31569번 - 세 수 XOR과 쿼리

문제

길이가 $N$인 정수 수열 $A_1,A_2,\dots,A_N$이 주어진다. 이때 다음 쿼리를 수행하는 프로그램을 작성해보자.

• 1ドル$ $l$ $r$ $x$: $A_i \oplus A_j \oplus A_k = x$ $(l \le i < j < k \le r)$를 만족시키는 순서쌍 $(i,j,k)$가 존재한다면 1, 존재하지 않으면 0을 출력한다. 여기서 $\oplus$는 Bitwise XOR 연산을 의미한다.
• 2ドル$ $l$ $r$ $x$: $l \le i \le r$인 모든 $i$에 대해 $A_i$를 $(A_i+x)\bmod 64$로 바꾼다.

입력

첫 번째 줄에 수열의 길이 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

두 번째 줄에 $N$개의 정수 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어진다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

출력

1ドル$번 쿼리에 대한 결괏값을 한 줄에 하나씩 입력으로 주어진 순서대로 출력한다.

제한

• 3ドル \le N \le 300,000円$
• 1ドル \le Q \le 300,000円$
• 0ドル \le A_i < 64$
• 1ドル \le l \le r \le N$
• 1ドル$번 쿼리에 한해서 $r-l+1 \ge 3$
• 0ドル \le x < 64$
• 입력으로 주어지는 모든 수는 정수이다.
• 1ドル$번 쿼리는 한 번 이상 주어진다.

노트

$A$를 음이 아닌 정수, $B$를 양의 정수라 할 때, $A \bmod B$는 $A$를 $B$로 나눈 나머지를 의미한다. 이 값은 음이 아닌 정수이다.