有 n 个人,由 1 至 n 编号。第 i(2≤i≤n) 个人有一个讨厌的人 fi(1≤fi<i),第 1 个人没有讨厌的人。
这一天,n 个人进行了一场关于投票的游戏。一次游戏会进行 n 轮。游戏开始时,所有人都没有被票出。游戏的每一轮中,会进行以下过程:
- 对于每一个没有被票出的人 i,TA 初始有 ai 票。
- 随后,对于每一个没有被票出的人 i,如果 TA 有讨厌的人且 TA 讨厌的人 fi 没有被票出,则 TA 会给 fi 投 bi 票。
- 最后,票出当前没有被票出的人的票数最高的,如果有多个票数最高的人,票出其中编号最大的人。
一次游戏的 n 轮之间独立计票。
在游戏开始前,发生了 q 次事件,事件有以下两种:
- 给定 p,x,y,将 (ap,bp) 修改为 (x,y);
- 小明想知道,给定两个人 c,d,如果此刻进行一次游戏,两个人中谁先被票出。
作为小明的朋友,你可以帮帮小明吗?
输入格式
从标准输入读入数据。
第一行两个正整数 n,q,表示人数与发生的事件数。
第二行 (n−1) 个整数 f2,f3,⋯,fn。
第三行 n 个整数 a1,a2,⋯,an。
第四行 n 个整数 b1,b2,⋯,bn。
接下来 q 行,每行三个或四个整数描述一个事件。第一个正整数 op 表示发生事件的类型。
- 若 op=1,则接下来三个整数 p,x,y,表示将 (ap,bp) 修改为 (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≤n,q≤2×105,
- ∀2≤i≤n,1≤fi<i,
- 0≤ai,bi,x,y≤108,
- 1≤c,d,p≤n,
- c≠d。
子任务编号 | 子任务分值 | n≤ | q≤ | 特殊性质 |
---|---|---|---|---|
1 | 5 | 500 | 500 | 无 |
2 | 10 | 3000 | 3000 | |
3 | 2×105 | 2×105 | fi 在 [1,i−1] 中均匀随机 | |
4 | 15 | fi=1 | ||
5 | 30 | fi=i−1 | ||
6 | 无 |