在贝尔兰,每个封建领地都拥有一座城堡,并且每座城堡都属于一个封建领地。
除一个封建国(国王)外,每个封建国都从属于另一个封建国。一个封建国家可以有任意数量的封臣(下属)。
有些城堡有道路相连,允许沿着道路双向移动。当且仅当其中一个城堡的所有者是另一个城堡所有者的直接下属时,两座城堡之间才有一条道路。
每年这两个事件中的一个可能会在 Berland 发生。
1. 野蛮人攻击城堡 c.有趣的是,在贝尔兰迪亚的整个历史中,野蛮人从未两次袭击过同一座城堡。
2. 一位高贵的骑士踏上了从城堡a到城堡b的旅程(前提是他在路上遇到每个城堡不超过一次)。
让我们详细考虑第二个事件。由于从a到b的路程并不短,那么骑士可能想在途中遇到的城堡停下来休息一下。然而,他不能随便停留在任何一座城堡:他的高贵不允许他留在被敌人恶臭亵渎的城堡里。一座城堡当且仅当它在 y 年之后受到攻击时才被亵渎。因此,骑士选择他遇到的第 k 个城堡,从 a 开始(不考虑城堡 a 和 b),从 y + 1 到当年,该城堡在几年内没有受到攻击。
骑士们不记得哪些城堡是在哪一年被袭击的,所以他请求宫廷学者,也就是你来帮助他们。伯兰历史上发生了一系列事件。告诉每个骑士,他应该在哪个城市停下来,否则就会传递出一个悲伤的消息——从a城市到b城市的路径上满足他要求的城市少于k个,所以骑士将无法休息。
输入
第一输入行包含整数 n (2 ≤ n ≤ 105) — 封建数量。
下一行包含 n 个空格分隔的整数:第 i 个整数显示第 i 个封建主的编号,如果第 i 个封建是国王,则显示 0。
第三行包含整数 m (1 ≤ m ≤ 105) — 查询数量。
然后遵循描述事件的 m 行。第 i 行(各行从 1 开始索引)包含对第 i 年发生的事件的描述。每个事件都由类型 ti (1 ≤ ti ≤ 2) 表征。第一类事件的描述看起来是两个空格分隔的整数 ti ci (ti = 1; 1 ≤ ci ≤ n),其中 ci 是第 i 年被野蛮人攻击的城堡的编号。第二种类型的描述包含五个空格分隔的整数:ti ai bi ki yi (ti = 2; 1 ≤ ai, bi, ki ≤ n; ai ≠ bi; 0 ≤ yi < i),其中ai是骑士出发的城堡的编号,bi是骑士要去的城堡的编号,ki和yi是第二个事件描述中的k和y。
您可以考虑索引从 1 到 n 的封建。保证了诸侯之中只有一位国王。保证对于第一类型事件,所有值 ci 都不同。
输出
对于每个第二类型事件,打印一个整数 - 骑士必须停留休息的城堡的编号,或者 -1,如果他必须不休息地走完从 ai 到 bi 的距离。用空格分隔答案。
按顺序打印答案,其中输入中给出了第二类型事件。
示例
输入 #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
输出 #1
2 -1 -1 2
输入 #2
6 2 5 2 2 0 5 3 2 1 6 2 0 1 2 2 4 5 1 0
输出 #2
5 -1
注意
在第一个示例中,骑士从城堡 1 到城堡 3 的路上只有城堡 2。当骑士第一次走过路径 1 - 3 时,城堡 2 不会被敌人亵渎,骑士会留在那里。在第二年,城堡 2 将被亵渎,因此骑士在接下来的两年中将无处可住(相应地,找到一座在第一年和第二年中没有被亵渎的城堡对他来说很重要)。第五年,骑士不会认为城堡2被亵渎,所以他会再次留在那里。