题目内容

小蓝有一个 $n \times n$ 的空白方格表，初始所有格子内的数值均为 $0$。她有两种操作：

• 行变换：选定第 $i$ 行，将该行所有格子的数值与行密钥 $a_i$ 按位异或；
• 列变换：选定第 $j$ 列，将该列所有格子的数值与列密钥 $b_j$ 按位异或。 两种操作的次数不限，可以按任意顺序进行。

现在知道操作结束后，位于对角线上（即第 $i$ 行第 $i$ 列，以下称为同标格）的 $n$ 个格子的最终数值依次为 $d_1, d_2, \dots, d_n$。给定 $q$ 次询问，每次给出一个行号 $u$ 和列号 $v$，你需要求出第 $u$ 行第 $v$ 列格子的最终数值。

已知行密钥 $a_1,\dots,a_n$ 互不相同，列密钥 $b_1,\dots,b_n$ 互不相同，且数据保证存在合法的操作序列使得同标格值恰好为给定的 $d_i$。方格表的维度 $n$ 与询问次数 $q$ 均满足 $1 \le n, q \le 10^5$，所有 $a_i$、$b_i$ 均为不超过 $10^6$ 的正整数，$d_i$ 满足 $0 \le d_i \le 10^6$。