#P18523. Game of Votes

Game of Votes

Game of Votes

有 nn 个人,编号为 1,2,…,n1,2,\ldots,n。对于每个 2≤i≤n2\le i\le n,第 ii 个人讨厌一个人 fif_i,其中 1≤fi<i1\le f_i<i。第 11 个人不讨厌任何人。

一天,他们参加了一个共进行 nn 轮的投票游戏。游戏开始时,没有人被淘汰。每一轮依次执行下列过程:

  1. 每个尚未被淘汰的人 ii 先获得 aia_i 票。
  2. 对于每个尚未被淘汰的人 ii,如果他讨厌的人 fif_i 也尚未被淘汰,那么他给 fif_i 投 bib_i 票。
  3. 在所有尚未被淘汰的人中,获得票数最多的人被淘汰。如果最多票数对应多个人,则淘汰其中编号最大的人。

各轮票数独立统计,上一轮的票数不会累积到下一轮。

在游戏开始之前发生了 qq 个事件,事件分为两类:

  1. 给定 p,x,yp,x,y,将 (ap,bp)(a_p,b_p) 修改为 (x,y)(x,y)。
  2. 给定两个不同的人 c,dc,d,询问:如果此刻用当前参数从头进行一场游戏,c,dc,d 中谁会先被淘汰?

请回答所有第二类事件。询问只要求计算结果,不会实际改变之后事件使用的参数,也不会保留任何淘汰状态。

输入格式

第一行包含两个正整数 n,qn,q(1≤n,q≤2×1051\le n,q\le2\times10^5),分别表示人数和事件数。

第二行包含 n−1n-1 个整数 f2,f3,…,fnf_2,f_3,\ldots,f_n,满足 1≤fi<i1\le f_i<i。当 n=1n=1 时,这一行没有整数。

第三行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 0≤ai≤1080\le a_i\le10^8。

第四行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,满足 0≤bi≤1080\le b_i\le10^8。

接下来 qq 行,每行描述一个事件:

  • 1 p x y:将 (ap,bp)(a_p,b_p) 修改为 (x,y)(x,y)。保证 1≤p≤n1\le p\le n,0≤x,y≤1080\le x,y\le10^8。
  • 2 c d:询问当前参数下,c,dc,d 中谁先被淘汰。保证 1≤c,d≤n1\le c,d\le n 且 c≠dc\ne d。

输入只有一组数据。

输出格式

对于每个第二类事件,输出一行一个字符。如果 cc 先被淘汰,输出 0;否则输出 1。

原题没有保证存在询问。因此,全为修改事件时应不输出任何内容;特别地,n=1n=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

输出:

0
0
1
1
1
1