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 ba \oplus b denotes the bitwise XOR operation between 22 integers aa and bb):

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

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


For all subtasks:

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

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

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

Subtask 1 [1/15]

1 \le N, Q \le 2\,0001 \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 = 0l = 0 and r = 5 \times 10^5r = 5 \times 10^5.

Subtask 4 [8/15]

No additional constraints.

Input Specification

The first line will contain two integers, NN and QQ.

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

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

Output Specification

For each query of type 33, 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\}\{1, 2\}. After our first operation, we have \{5, 6\}\{5, 6\}. The first type 33 operation outputs 5 \oplus 6 = 35 \oplus 6 = 3 while the second one outputs 5=55=5.


There are no comments at the moment.