#P18574. XOR of All Children
XOR of All Children
XOR of All Children
给定一棵有 个顶点的有根树,每个顶点上有一个整数。
每过一秒,所有顶点的值同时更新:一个顶点的新值,等于它当前的值与它的所有直接孩子当前值的异或。也就是说,计算这一秒的所有新值时,都使用更新前的值。
有 个相互独立的询问。每个询问给出 ,请计算从最初状态开始恰好经过 秒后,顶点 上的值。
输入格式
第一行包含两个整数 (,),分别表示顶点数和询问数。
第二行包含 个整数 (),表示各顶点的初始值。最大可能值为 。
第三行包含 个整数 (),其中 是顶点 的父亲,顶点 为根。 时这一行没有整数。
接下来 行,每行包含两个整数 (,),描述一个询问。
输入只有这一棵树,不含测试组数。所有询问都从给定的初始数组出发,不承接上一个询问的时间或状态。
输出格式
对每个询问输出一行一个整数,表示顶点 在经过 秒后的值。按照普通非负十进制整数输出;异或结果仍在 内。
样例
输入
7 9
5 3 6 1 4 7 2
1 1 2 2 3 3
1 0
1 1
1 2
2 1
2 2
3 3
4 5
5 2
6 1
输出
5
0
5
6
3
3
1
4
7