有 $n$ 个人，编号为 $1$ 到 $n$。对于 $2 \le i \le n$，第 $i$ 个人讨厌一个人 $f_i$ ($1 \le f_i < i$)，而第 $1$ 个人不讨厌任何人。

某天，这 $n$ 个人参加了一个投票游戏，游戏共包含 $n$ 轮。游戏开始时，没有人被淘汰。在游戏的每一轮中，会发生以下过程：

1. 每个尚未被淘汰的人 $i$ 初始拥有 $a_i$ 票。
2. 然后，对于每个尚未被淘汰且讨厌某人（且该被讨厌的人 $f_i$ 也尚未被淘汰）的人 $i$，他会为 $f_i$ 投出 $b_i$ 票。
3. 最后，在所有尚未被淘汰的人中，票数最高的人被淘汰。如果有多个人的票数最高，则编号最大的人被淘汰。

游戏中的每一轮都会独立统计票数。

在游戏开始前，会发生 $q$ 个事件，事件分为以下两种类型：

1. 给定 $p, x, y$，将 $(a_p, b_p)$ 修改为 $(x, y)$；
2. 小明想知道，给定两个人 $c, d$，如果此时进行一场游戏，这两个人中谁会先被淘汰。

作为小明的朋友，你能帮帮他吗？

输入格式

第一行包含两个正整数 $n$ 和 $q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示人数和发生的事件数。

第二行包含 $(n - 1)$ 个整数 $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$)。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^8$)。

第四行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 10^8$)。

接下来的 $q$ 行，每行包含三个或四个整数描述一个事件。第一个正整数 $op$ 表示事件类型。

• 如果 $op = 1$，则后面跟着三个整数 $p, x, y$ ($0 \le x, y \le 10^8, 1 \le p \le n$)，表示将 $(a_p, b_p)$ 修改为 $(x, y)$。
• 如果 $op = 2$，则后面跟着两个正整数 $c, d$ ($1 \le c, d \le n, c \neq d$)，你需要确定如果此时进行一场游戏，在 $c$ 和 $d$ 之间谁会先被淘汰。

输出格式

对于每个 $op = 2$ 的事件，输出一行一个字符。如果 $c$ 先被淘汰，输出“0”，否则输出“1”。

样例

样例输入 1

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

样例输出 1

0
0
1
1
1
1