3040: 树上路径

古时候帝国有n个城堡，编号从1到n。除了皇帝拥有的城堡之外，其他每个城堡都从属于某个城堡。如果两个城堡有直接从属关系，则有一条双向路径连接两个城堡，保证整个帝国的所有城堡互相可达。每一年，野蛮人有可能对某一个城堡c发起攻击，所到之处，寸草不生。此外，野蛮人不会对同一个城堡发起多次攻击。如果某一年野蛮人没有攻击，则骑士就会出来巡逻，巡逻路线是从城堡a到城堡b且不会多次经过同一个城堡。在巡逻时，骑士需要休息，但是他不会选择最近y年被攻击的城堡休息。具体地说，城堡a到城堡b（不含a和b）的路线中，第k个在y+1年后没被攻击的城堡会被骑士选做休息地点。你的任务就是计算每次骑士巡逻的休息地点。

第一行一个整数n，表示城堡数。第二行n个整数，第i个数a[i]表示城堡i从属于城堡a[i]，若为0，表示第i个城堡是皇帝的城堡。第三行一个整数m，表示总年数。以下m行，其中第i行表示第i年的事件，用第一个数表示事件类型：1 c[i]：第i年野蛮人攻击城堡c[i]；2 a[i] b[i] k[i] y[i]：含义同题面，满足1<=a[i], b[i], k[i]<=n；0<=y[i]<i。

每一次骑士巡逻的休息地点的城堡编号单独输出一行，若不需休息，则输出-1。

3
0 1 2
5
2 1 3 1 0
1 2
2 1 3 1 0
2 1 3 1 1
2 1 3 1 2

2
-1
-1
2