Riolku's Mock CCC S5 - Keen Keener Multiset

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Keen Kena Googler the Keener was keen to try out some queries on the new multiset he got for his birthday, until he realized that he seemed to be getting incorrect answers for his queries. Thus, he decided to write a program that simulates the queries he's trying to perform on the multiset. However, his program wasn't very efficient, and he hopes that you might be able to help him write a better one.

His multiset supports the following queries (Note: a \oplus b denotes the bitwise XOR operation between 2 integers a and b):

  • 1 x: Insert the integer x into the multiset.
  • 2 l r x: For every integer a in the multiset where l \le a \le r, replace it with a \oplus x.
  • 3 l r: Let a_1, a_2, \dots, a_k be all integers in the multiset where l \le a_i \le r. Output the value a_1 \oplus a_2 \oplus \dots \oplus a_k.

Write a program that can support Q queries of the above types.


For all subtasks:

1 \le N, Q \le 2 \times 10^5

0 \le a_i, x \le 2 \times 10^5

0 \le l \le r \le 5 \times 10^5

Subtask 1 [1/15]

1 \le N, Q \le 2\,000

Subtask 2 [2/15]

There will be no operations of the type 2 l r x.

Subtask 3 [4/15]

For all operations of the type 2 l r x, l = 0 and r = 5 \times 10^5.

Subtask 4 [8/15]

No additional constraints.

Input Specification

The first line will contain two integers, N and Q.

The next line will contain N space-separated integers, the initial elements of Keen Kena Googler the Keener's multiset.

The next Q lines will each contain a query of one of the above three types.

Output Specification

For each query of type 3, output its answer on a separate line.

Sample Input

2 3
1 2
2 0 3 4
3 2 9
3 5 5

Sample Output


Sample Explanation

Our initial multiset contains \{1, 2\}. After our first operation, we have \{5, 6\}. The first type 3 operation outputs 5 \oplus 6 = 3 while the second one outputs 5=5.


There are no comments at the moment.