XOR Divisor Sugoroku

問題文

$1$ 以上 $N$ 以下の整数 $i$ それぞれに、整数 $A_i$ が書かれています。

あなたは以下の $Q$ 個のクエリを処理してください。

各クエリでは、整数 $X,Y$ が与えられます。

はじめ、あなたは整数 $X$ にいます。

現在いる整数を $x$ とするとき、$x>1$ である限り、次の操作を好きな回数行うことができます。

• $x$ の 自身を除いた正の約数 $d$ をひとつ選び、整数 $d$ へ移動する。

この操作を繰り返し、最終的に整数 $1$ へ到達するような移動によって訪れた整数列を

$$x = (x_0 = X,x_1,\ldots,x_k=1)$$

とします。

このとき、この移動方法の スコア を

$$Y\oplus A_{x_0}\oplus A_{x_1}\oplus\cdots\oplus A_{x_k}$$

と定めます。

ここで $\oplus$ はビット単位 XOR を表します。

整数 $1$ へ到達する移動方法すべてのうち、スコアの最小値を求めてください。

制約

• $1\le N\le 2\times 10^4$
• $1\le Q\le 2\times 10^5$
• $0\le A_i<64$
• $1\le X\le N$
• $0\le Y<64$
• 入力される値はすべて整数

入力

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

出力

$Q$ 行出力してください。

$i$ 行目には、$i$ 番目のクエリにおけるスコアの最小値を出力してください。

入力例

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

出力例

4
0
4

説明

1 個目のクエリ

$X=6,Y=0$ です。

この場合の移動方法は $3$ 通り考えられます。

$6\to1$ と移動すると、スコアは

$$0\oplus A_6\oplus A_1 = 0\oplus6\oplus1 = 7$$

です。

$6\to2\to1$ と移動すると、

$$0\oplus A_6\oplus A_2\oplus A_1 = 0\oplus6\oplus2\oplus1 = 5$$

です。

$6\to3\to1$ と移動すると、

$$0\oplus A_6\oplus A_3\oplus A_1 = 0\oplus6\oplus3\oplus1 = 4$$

です。

したがって、スコアの最小値は $4$ です。

2 個目のクエリ

$X=6,Y=7$ です。 $6\to1$ と移動すると、スコアは

$$7\oplus6\oplus1=0$$

となります。

スコアは非負整数なので、これより小さくすることはできません。したがって答えは $0$ です。