有 $n$ 个人，由 $1$ 至 $n$ 编号。第 $i (2 \le i \le n)$ 个人有一个讨厌的人 $f_i (1 \leq f_i < i)$，第 $1$ 个人没有讨厌的人。
这一天，$n$ 个人进行了一场关于投票的游戏。一次游戏会进行 $n$ 轮。游戏开始时，所有人都没有被票出。游戏的每一轮中，会进行以下过程：
1. 对于每一个没有被票出的人 $i$，TA 初始有 $a_i$ 票。
2. 随后，对于每一个没有被票出的人 $i$，如果 TA 有讨厌的人且 TA 讨厌的人 $f_i$ 没有被票出，则 TA 会给 $f_i$ 投 $b_i$ 票。
3. 最后，票出当前没有被票出的人的票数最高的，如果有多个票数最高的人，票出其中编号最大的人。
一次游戏的 $n$ 轮之间独立计票。
在游戏开始前，发生了 $q$ 次事件，事件有以下两种：
1. 给定 $p, x, y$，将 $(a_p, b_p)$ 修改为 $(x,y)$；
2. 小明想知道，给定两个人 $c,d$，如果此刻进行一次游戏，两个人中谁先被票出。
作为小明的朋友，你可以帮帮小明吗？
## Input
从标准输入读入数据。
第一行两个正整数 $n, q$，表示人数与发生的事件数。
第二行 $(n-1)$ 个整数 $f_2, f_3, \cdots, f_n$。
第三行 $n$ 个整数 $a_1, a_2, \cdots, a_n$。
第四行 $n$ 个整数 $b_1, b_2, \cdots, b_n$。
接下来 $q$ 行，每行三个或四个整数描述一个事件。第一个正整数 $op$ 表示发生事件的类型。
- 若 $op=1$，则接下来三个整数 $p, x, y$，表示将 $(a_p, b_p)$ 修改为 $(x, y)$。
- 若 $op=2$，则接下来两个正整数 $c, d$，你需要判断如果此时进行了一次游戏，$c$ 和 $d$ 谁先被票出。
## Output
输出到标准输出。
对于每个 $op=2$ 的事件输出一行一个 `01` 字符，若 $c$ 先被票出输出 `0`，否则输出 `1`。
[samples]
## Note
对于所有测试数据，
- $1 \le n, q \le 2 \times 10^5$，
- $\forall 2 \le i \le n, 1 \le f_i < i$，
- $0 \le a_i, b_i, x, y \le 10^8$，
- $1 \le c, d, p \le n$，
- $c \ne d$。
| 子任务编号 | 子任务分值 | $n \leq$ | $q \leq$ | 特殊性质 |
|-------|-------|-----------------|-----------------|----------------------------|
| 1 | 5 | $500$ | $500$ | 无 |
| 2 | 10 | $3000$ | $3000$ | 无 |
| 3 | 10 | $2 \times 10^5$ | $2 \times 10^5$ | $f_i$ 在 $[1, i - 1]$ 中均匀随机 |
| 4 | 15 | $2 \times 10^5$ | $2 \times 10^5$ | $f_i = 1$ |
| 5 | 30 | $2 \times 10^5$ | $2 \times 10^5$ | $f_i = i-1$ |
| 6 | 30 | $2 \times 10^5$ | $2 \times 10^5$ | 无 |