2315. [HZOI 2015]奈特

【题目描述】

我们有n个城市，这些城市的关系组成了一棵有根树，首都是树根

要求你支持以下操作：

第i个操作有以下两种形式：

1、1 u 表示在第i个时刻u这个城池被野蛮人的军队暴揍了一顿

2、2 u v k val

这个操作表示国王将从u城池走到v城池，但是这个国王是处女座

所以他只会在没有被揍过的城市或者这个城市被揍的时刻<=val的城市中停留休息

又因为这个国王很懒，所以他能休息就一定会休息

现在国王希望每次出行前都能知道他第k个休息的城市的编号是多少

如果他休息不足k次就可以到达v城池，请输出-1

由于野蛮人很奇怪，所以野蛮人不会暴揍一个城池两次或两次以上

注意国王并不会在起点和终点休息

【输入格式】

第一行输入n表示节点数量

以下n个正整数分别表示每个城市的父亲，父亲为0的节点为首都

之后输入m表示操作次数

以下m个操作如题意所示

数据保证每个城池最多会被揍过一次

数据保证u!=v,数据保证当第i个操作是第二种操作时，0<=val<=i

数据保证n，m<=100000

【输出格式】

对于第二种操作输出相应的答案

【样例输入】

样例输入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：

6

2 5 2 2 0 5

3

2 1 6 2 0

1 2

2 4 5 1 0

【样例输出】

样例输出1：

2

-1

-1

2

样例输出2：

5

-1