Migrated from Lutece 2932 Princess Principal

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag:树链剖分/LCT

“有的谎言说着说着也就变成了真实。”

安洁是一名来自黑蜥蜴星的间谍。 什么？你问黑蜥蜴星在哪里？我也不知道。 总之今天安洁也作为一名优秀的间谍在阿尔比恩王国活跃着。 这一次安洁需要潜入一名王族的宅邸盗取机密文件。这个宅邸有$n$个房间，编号从$1$到$n$，宅邸的结构可以用有根树（即$n$个点$n-1$条边的连通图）来描述：树上每一个点代表了宅邸的一个房间，如果两个点之间有边相连，说明这两个点代表的房间可以直接相互到达，其中根节点为1号点。宅邸内的某些房间有警卫巡逻，称为监控区；某些房间没有警卫巡逻，称为盲区。由于安洁伪装成了宅邸里的女仆，因此她并不担心被警卫看见，在监控区和盲区都可以自由移动。但是当安洁从监控区移动到盲区，或者从盲区移动到监控区时，会引起警卫额外的关注。安洁希望低调行事，任何移动时都不引起警卫的额外的关注。安洁移动所需的时间忽略不计。 安洁潜入前摸清了宅邸结构，并对每个房间搜索的优先程度进行了预估，用正整数$a_i$表示。$a_i$越小，表示该房间的优先级越高，越优先搜索。 在整个潜入过程中，警卫随时可能会进入或者离开某个房间，同时安洁也会对某些房间的优先程度$a_i$不断修正。 现在，安洁希望你可以协助她完成这次行动。整个潜入行动过程可以概括为$m$个事件，包含三种不同类型的事件：

1. 修改操作：给定一个参数$u$，表示房间$u$状态发生了变化。如果房间$u$里原本有警卫，则表示警卫离开了房间$u$；如果房间$u$里原本没有警卫，则表示有警卫进入了房间$u$。
2. 修改操作：给定两个参数$u$和$x$，表示安洁对房间$u$的优先程度重新进行了评估，优先程度$a_u$改为$x$。
3. 询问操作：给定参数$u$，表示安洁进行了一次假设性的询问：如果此时安洁在房间$u$，则她通过移动能到达的最优先搜索的房间的优先程度是多少。

Input

输入第一行包含一个整数$n$，表示宅邸的房间个数。 输入第二行包含$n$个整数，第$i$个整数表示了第$i$个房间初始的状态。若该整数为$1$，表示这个房间刚开始有警卫巡逻，为监控区；若该整数为$0$，表示这个房间刚开始没有警卫巡逻，为盲区。 输入第三行包含$n$个整数，第$i$个整数表示第$i$个房间的优先程度$a_i$。 输入第四行包含了$n-1$个整数，描述了宅邸结构，第$i$个的整数表示第$i+1$个房间的父节点房间编号$f_i$。 输入第五行包含一个整数$m$，表示潜入过程中发生了$m$个事件。 接下来$m$行，每行用若干个整数描述了一个事件，其中第一个整数记作$opt$，表示事件类型。 若$opt=1$，则接下来有一个整数$u$，表示房间$u$的状态发生了变化。如果房间$u$此时有警卫巡逻，则警卫离开了房间$u$；如果房间$u$此时没有警卫巡逻，则表示有警卫进入了房间$u$。 若$opt=2$，则接下来有两个整数$u$和$x$，表示安洁重新评估了房间$u$，将房间$u$的优先程度$a_u$改为了$x$。 若$opt=3$，则接下来有一个整数$u$，表示安洁进行了一次假设性的询问：如果安洁此时在房间$u$，则她通过移动能到达的最优先搜索的房间的优先程度是多少。

Output

对于每一个询问事件($opt=3$)，输出一行一个整数表示答案。

Samples

10
1 0 0 1 0 0 0 1 0 1
5 2 1 1 3 1 4 5 2 1
1 1 1 2 3 3 4 6 6
9
3 1
3 2
3 3
3 10
1 3
1 6
3 10
2 9 5201314
3 9

1
2
1
1
1
5201314

Constraints

$1\le n,m\le 5*10^5,1\le u\le n,1\le a_i,x\le 10^9(1\le i\le n),1\le f_i< i(2\le i\le n)$

Resources

2023 UESTC ICPC Training for Data Structures