22417번 - Bit Operation Game 다국어

문제

$N$ 頂点の根付き木が与えられる。 頂点には 0ドル$ から $N-1$ の番号がついており、0ドル$番目の頂点が根を表す。 根には T = 0 が、それ以外の頂点には

• T=T&X
• T=T&Y
• T=T|X
• T=T|Y
• T=T^X
• T=T^Y

のいずれかの操作が書かれている。 ここでの演算子 &, |, ^ はそれぞれビット演算子 and, or, xor, を意味する。

A君とB君はこの木を使って以下のゲームを $M$ 回行った。 二人は根からスタートし、子頂点を選び進むという操作を、A君から始め葉に到達するまで交互に行う。 通ったノードに書かれている操作を、通った順に適用した時の、最終的な $T$ の値がスコアになる。 B君はできるだけスコアを小さくしたいと考えており、またA君は大きくしたいと考えている。 M回のゲームの $X,ドル $Y$ の値が与えられるので、二人が最適な選択をした時の各ゲームのスコアを出力せよ。

입력

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$o_1$

$o_2$

$...$

$o_{N-1}$

$u_1$ $v_1$

$u_2$ $v_2$

$...$

$u_{N-1}$ $v_{N-1}$

$X_1$ $Y_1$

$X_2$ $Y_2$

$...$

$X_M$ $Y_M$

1ドル$ 行目には木の頂点数 $N$ と、行われるゲーム数を表す整数 $M$ が入力される。

2ドル$ 行目から $N$ 行目にかけて、1ドル$ 〜 $N-1$ 番目の頂点に書かれている操作が入力される。

さらに続けて $N-1$ 行に、各辺により繋がれる 2ドル$ 頂点の番号が入力される。

最後に $M$ 回のゲームにおける $X,ドル $Y$ の値が $M$ 行に渡り入力される。

출력

各ゲームでの最終的な $T$ の値をそれぞれ $M$ 行に出力せよ。

제한

• 1ドル \leq N \leq 100000$
• 1ドル \leq M \leq 100000$
• 0ドル \leq X, Y < 2^{16}$

힌트