P3445.第2题-矩阵的主对角线
题目内容
小杰有一个 n×n 的矩阵，和两个由 n 个互不相同的整数组成的数组 {x1,x2,...,xn} 和 {y1,y2,...,yn} 。
为了方便描述，我们使用 aij 表示矩阵的第 i 行第 j 列的元素。起初，矩阵中每个元素都等于 0 ，直到他对矩阵进行了若干次以下两种操作(次数未知)：
现在已知主对角线从左上角到右下角第 i 个位置的最终值为 zi ，需要回答 q 次询问，每次你需要求出 au,v 的元素值。
【名词解释】
矩阵的主对角线为从左上角到右下角的直线，即所有满足 i=j 的元素 aij 组成的集合。
输入描述
第一行输入两个整数 n 和 q(1≦n,q≦105) ，分别表示矩阵的维度和询问次数；
第二行输入 n 个互不相同的整数 x1,x2,….,xn(1≦xi≦106) 代表行异或值；
第三行输入 n 个互不相同的整数 y1,y2,….,yn(1≦yi≦106) 代表行异或值；
第四行输入 n 个整数 z1,z2,….,zn(0≦zi≦106) ，表示主对角线的最终值；
此后 q 行，每行输入两个整数 u 和 v(1≦u,v≦n) ，表示询问的位置。
除此之外，保证 xi 和 yi 的值互不相同。
输出描述
对于每次询问，新起一行。输出一个整数，表示询问的元素值。保证输入的 zi 值与至少一种有效的操作序列对应。
如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。
样例1
输入
2 1
1 2
3 4
1 4
1 2
输出
5
说明
在这个样例中，矩阵的其中一种合法的变化过程为：
样例2
输入
3 2
1 2 4
8 16 32
1 16 36
1 3
2 3
输出
33
32
