有 $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$，如果此刻进行一次游戏，两个人中谁先被票出。

作为小明的朋友，你可以帮帮小明吗？

输入格式

从标准输入读入数据。

第一行两个正整数 $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$ 谁先被票出。

输出格式

输出到标准输出。

对于每个 $op=2$ 的事件输出一行一个 01 字符，若 $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

子任务

对于所有测试数据，

• $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$。