409751: GYM103729 E Multigate

Rainbow Dash is a Pegasus pony who loves adventure.

One day, she comes across a sequence of $$$n$$$ magic gates, each magic gate has a magic power value $$$a_i$$$ and a type $$$b_i$$$.

Initially, Rainbow Dash has a integer $$$x$$$ in her hands. When Rainbow Dash passes through the $$$i$$$-th magic gate with a non-negative integer $$$x$$$, $$$x$$$ will become $$$x \ \texttt{OR} \ a_i$$$ if $$$b_i$$$ is $$$1$$$ and otherwise $$$x \ \texttt{AND} \ a_i$$$ if $$$b_i$$$ is $$$0$$$, here $$$\texttt{OR}$$$ and $$$\texttt{AND}$$$ mean bitwise OR and bitwise AND respectively. Additionally, she must pass through the gate according to the given order.

Since Rainbow Dash has some unicorn friends, she could choose at most $$$k$$$ magic gates and flip the $$$b_i$$$ of these magic gates before she goes. That means, she could flip $$$b_i$$$ to $$$1$$$ if $$$b_i = 0$$$ originally and vice versa.

Rainbow Dash needs to maximize the integer $$$x$$$ after passing $$$n$$$ magic gates. However, she will face this challenge $$$q$$$ times independently, and each time she is given two non-negative integers $$$x$$$ and $$$k$$$, which means the initial number in her hands and the maximum times of flip operations she could use. Please pay attention that the flip operation in one challenge will not influence another challenge.

The first line contains two integers $$$n\ (1\le n\le 2\times 10^5)$$$ and $$$q\ (1\le q\le 2\times 10^5)$$$ - the length of array $$$a$$$ and the numbers of queries.

The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n\ (0\le a_i< 2^{30})$$$ - the elements of array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n\ (0\le b_i\le 1)$$$ - the elements of array $$$b$$$.

The next $$$q$$$ lines, each line contains two integer $$$x\ (0\le x<2^{30})$$$ and $$$k\ (0\le k\le n)$$$ - the initial number and the most flip operation she could use.

For each test case, output a single line containing the maximum possible $$$x$$$ after performing at most $$$k$$$ operations and passing the magic gates.

4 7
3 1 3 5
0 1 0 0
6 0
6 1
7 0
7 1
7 2
2 0
2 1

1
7
1
7
7
1
7

For the query $$$1$$$, there is no flip chance and $$$x$$$ will pass the following process:

$$$((((6\ \texttt{AND}\ 3) \ \texttt{OR}\ 1) \texttt{AND}\ 3) \ \texttt{AND} \ 5)=1$$$.

For the query $$$2$$$, Rainbow Dash could flip the $$$4$$$-th magic gate and $$$x$$$ will finally become $$$7$$$, which is maximal.

Query $$$3$$$ and query $$$6$$$ is familiar to query $$$1$$$, which have no flip chance.

Query $$$4$$$ and query $$$8$$$ is familiar to query $$$2$$$, which have to flip the $$$4$$$-th magic gate to get $$$x$$$ maximal.

As for query $$$5$$$, flipping the $$$3$$$-rd magic gate and $$$4$$$-th magic gate would be the best choice.