XOR of Three Numbers and Queries

Time limit2sMemory limit1024 MB

Summary

Given an array of values below 64, answer whether some three distinct positions in a range XOR to x, and support adding x mod 64 to every element in a range.

Level: Medium7 of 10
Topics: Segment tree, Bit manipulation, Implementation
Solved: No attempts yet

Problem

A sequence of integers $A_1, A_2, \dots, A_N$ of length $N$ is given. Write a program that processes the following two kinds of queries.

1 $l$ $r$ $x$ : Print 1 if there is an ordered triple $(i,j,k)$ with $l \le i < j < k \le r$ such that $A_i \oplus A_j \oplus A_k = x$ . Otherwise, print 0. Here, $\oplus$ is the Bitwise XOR operation.
2 $l$ $r$ $x$ : For every $i$ with $l \le i \le r$ , replace $A_i$ with $(A_i+x) \bmod 64$ .

Input

The first line contains $N$ and $Q$ , separated by a space.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ , separated by spaces.

Each of the next $Q$ lines contains one query.

Output

For each query of type 1, print the result on its own line, in the order the queries are given.

Constraints

$3 \le N \le 300\,000$
$1 \le Q \le 300\,000$
$0 \le A_i < 64$
$1 \le l \le r \le N$
For type 1 queries, $r-l+1 \ge 3$ .
$0 \le x < 64$
All numbers in the input are integers.
The input contains at least one query of type 1.

Hint

Let $A$ be a nonnegative integer and $B$ a positive integer. Then $A \bmod B$ is the remainder when $A$ is divided by $B$ . This value is a nonnegative integer.

Examples1

Example 1

Input

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

Expected output