세 수 XOR과 쿼리

시간 제한2초메모리 제한1024 MB

요약

값이 64 미만인 배열에서 구간 내 서로 다른 세 원소의 XOR이 x인지 판별하고, 구간의 각 원소에 x를 더해 64로 나눈 나머지로 바꿉니다.

문제

길이가 $N$ 인 정수 수열 $A_1, A_2, \dots, A_N$ 이 주어진다. 다음 두 종류의 쿼리를 처리하는 프로그램을 작성하시오.

1 $l$ $r$ $x$ : $l \le i < j < k \le r$ 을 만족하는 순서쌍 $(i,j,k)$ 중 $A_i \oplus A_j \oplus A_k = x$ 인 것이 존재하면 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인 쿼리마다 결과를 주어진 순서대로 한 줄에 하나씩 출력한다.

$A$ 를 음이 아닌 정수, $B$ 를 양의 정수라 하자. $A \bmod B$ 는 $A$ 를 $B$ 로 나눈 나머지이며, 이 값은 음이 아닌 정수이다.

예제 1

입력

8 6
1 2 4 5 0 1 1 2
1 1 4 0
1 6 8 1
1 1 4 8
2 4 5 3
1 3 6 10
1 3 6 12

예상 출력