410778: GYM104101 K Bit

$$$Hile$$$ wants to play a game with you. First, you can select a number $$$x$$$ in the range of $$$[0, r]$$$.

Then $$$Hile$$$ will perform $$$n$$$ operations on the number $$$x$$$ you select, each of which is of one of the following three types:

• $$$1 \ \ a$$$ : change $$$x$$$ to $$$x\ \&\ a$$$, which $$$\&$$$ means bitwise AND.

• $$$2 \ \ a$$$ : change $$$x$$$ to $$$x\ |\ a$$$, which $$$|$$$ means bitwise OR.

• $$$3 \ \ a$$$ : change $$$x$$$ to $$$x \oplus a$$$, which $$$\oplus$$$ means bitwise XOR.

Assume that $$$y$$$ is obtained by $$$x$$$ after $$$n$$$ operations. $$$Hile$$$ will ask you $$$q$$$ questions. For each question, the operations are fixed, and he will give you a number $$$r$$$ — the range. You should tell her which $$$x$$$ $$$(0 \le x \le r)$$$ you choose initially to maximize the final $$$y$$$.

The first line of the input contains two integers $$$n, q$$$ $$$(1\le n\le 2\times 10^5, 1\le q\le 2 \times 10^5)$$$ — The number of operations and the number of questions.

The next $$$n$$$ lines each line contains two integers $$$t, a$$$ $$$(1 \le t \le 3, 0 \le a < 2^{30})$$$ — the operation type and the number.

The next $$$q$$$ lines each line contains one integer $$$r$$$ $$$(1 \le r < 2^{30})$$$ — The number $$$Hile$$$ gives you.

Output $$$q$$$ lines — for each $$$r$$$, you should output which $$$x$$$ $$$(0 \le x \le r)$$$ you choose initially that $$$y$$$ is maximize possible.

If there are multiple answers, print any of them.

3 5
1 2
2 1
3 4
1
2
3
4
5

0
2
3
3
2

In the test case:

If choose $$$x = 0$$$, $$$y = ((0\ \&\ 2)\ |\ 1) \oplus 4 = 5$$$.

If choose $$$x = 1$$$, $$$y = ((1\ \&\ 2)\ |\ 1) \oplus 4 = 5$$$.

If choose $$$x = 2$$$, $$$y = ((2\ \&\ 2)\ |\ 1) \oplus 4 = 7$$$.

If choose $$$x = 3$$$, $$$y = ((3\ \&\ 2)\ |\ 1) \oplus 4 = 7$$$.

If choose $$$x = 4$$$, $$$y = ((4\ \&\ 2)\ |\ 1) \oplus 4 = 5$$$.

If choose $$$x = 5$$$, $$$y = ((5\ \&\ 2)\ |\ 1) \oplus 4 = 5$$$.

When $$$r = 1$$$, you can choose $$$x = 0$$$ or $$$x = 1$$$.

When $$$r = 2$$$, you can choose $$$x = 2$$$.

When $$$r \ge 3$$$, you can choose $$$x = 2$$$ or $$$x = 3$$$.