有 $n$ 个人，由 $1$ 至 $n$ 编号。第 $i(2\le i\le n)$ 个人有一个讨厌的人 $f_i(1\le 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

样例输入 #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$，
• $\mathrm{\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$。

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$