题目描述

小 D 刚刚学习了逻辑运算。在逻辑表达式中， 用 0 表示逻辑假， 用 1 表示逻辑真，用 and, or, not 分别表示逻辑与、逻辑或、逻辑非运算。比如：0 and 1 = 0、0 or 1 = 1、not 0 = 1。

现在小 D 在探究一种逻辑运算 nand：定义 a nand b = not(a and b)。nand 运算从左往右执行 ， 所 以 a nand b nand c = ( a nand b) nand c。

经过探究，小 D 发现了 nand 运算的一些性质， 比如：- nand 运算不满足结合律：可能会有 (anand b)nand c ≠ anand(bnand c) 。- 可以只使用 nand 运算来表示任意其他的逻辑运算，比如 (anand b) nand (anand b) = aand b，(anand a) nand( bnand b) = a or b。

为了研究 nand 运算的更多性质，小 D 开始思考这样一个问题：

有一颗 n 个点的有根树， 以点 1 为根。树上的每个点上有一个数字，为 0 或者 1。现在要从点 u 先走到根，再走到点 u，每经过一个点，就将点上的数字加入一个序列 $a$ 的末尾。在得到的序列 $a_1 , a_2 , . . . , a_l$ 的相邻的数之间插入 nand 运算，得到的逻辑表达式 $a_1$ nand $a_2$ nand……nand $a_l$ 的值是多少？

小 D 想不明白这个问题， 于是决定让你来回答。小 D 有 $m$ 次询问，每次给出两个点 $u, v$，你需要回答他的每一次询问。特别地， 如果得到的序列 $a$ 只有一个数，则答案为这个数。

输入格式

从文件 $logical.in$ 中读入数据。 第一行包含两个整数 $n, m$，分别表示树的点数和询问的个数。 之后一行包含 $n − 1$ 个整数，其中第 $i$ 个整数表示点 $i + 1$ 在树上的父节点。 之后一行包含 $n$ 个整数，为 $0$ 或者 $1$，其中第 $i$ 个整数表示点 $i$ 上的数字。 之后 $m$ 行，每行包含两个整数 $u, v$，表示一次询问。

输出格式

输出到文件 $logical. out$ 中。 输出 $m$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次询问的答案。

样例 #1

样例输入 #1

5 4
1 1 3 3
0 0 1 0 1
5 4
2 4
1 5
5 1

样例输出 #1

1
1
0
1

样例 #2

样例输入 #2

见 选 手 目 录 下 的 logical/ logical2 . in。

样例输出 #2

见 选 手 目 录 下 的logical/ logical2 . ans。

样例 #3

样例输入 #3

见 选 手 目 录 下 的 logical/ logical3 . in 。

样例输出 #3

见 选 手 目 录 下 的  logical/ logical3 . ans。

提示

样例1解释 ：

• 第 1 次询问：路线为 5 → 3 → 1 → 3 → 4，得到的序列 a 为 1, 1, 0, 1, 1，答案为1 nand 1 nand 0 nand 1 nand 1 = 1。

• 第 2 次询问： 路线为 2 → 1 → 3 → 5，得到的序列 a 为 0, 0, 1, 1，答案为0 nand 0 nand 1 nand 1 = 1。

• 第 3 次询问：路线为 1 → 3 → 5，得到的序列 a 为 0, 1, 1，答案为 0 nand 1 nand 1 =0。

• 第 4 次询问：路线为 5 → 3 → 1，得到的序列 a 为 1, 1, 0，答案为 1 nand 1 nand 0 =1。

样例2提示 ： 该样例满足测试点 4 的限制。

样例3提示 ： 该样例满足测试点 20 的限制。

数据范围： 对于所有测试数据，保证： $1 ≤ n, m ≤ 3 × 10^5 ，1 ≤ p_i < i，1 ≤ u, v ≤ n$。