给定一棵大小为 n 的 1 为根节点的树,树用如下方式给出:输入 a2,a3,…,an,保证 1≤ai<i,将 ai 与 i 连边形成一棵树。
接下来有 m 次操作,操作有两种:
1 l r x
令 ai=max。2 u v
查询在当前的 a 数组构成的树上 u,v 的 LCA。
输入格式
第一行包含两个数 n,m。
之后一行 n-1 个数,表示 a_2,...,a_n。
之后 m 行,每行三个或四个数,表示一次操作。
本题强制在线,所有输入的 l,r,x,u,v 均需要异或 lastans,其定义为上一次询问操作得到的答案,若之前没有询问操作,则为 0。
输出格式
对于每个 2 操作,输出一行一个数表示答案。
样例数据
样例输入
6 4
1 2 3 3 4
2 3 4
1 1 0 2
2 6 5
2 1 0
样例输出
3
3
1
子任务
Idea:Ynoi,Solution:Ynoi,Code:Ynoi,Data:Ynoi&nzhtl1477
对于 100\% 的数据,满足 2\leq n,q\leq 4\times 10^5,2\leq l\leq r\leq n,1\leq x\leq 4\times 10^5,1\leq u,v\leq n。