圣诞节就要到了,小C想买一棵圣诞树。自然,请客请到破产的小C买不起圣诞树,所以,小C计划把过年用的许愿树改造成圣诞树。
许愿树是一棵
我们定义一次单旋为:
假设
如果是右孩子,就做其轴对称操作。
圣诞树支持如下三个操作:
- 点
连续不断单旋向上,直至它成为点 的儿子,保证 是 的祖先 - 询问点
的第 级祖先,保证此时点 的第 级祖先存在 - 询问整棵树先序遍历中的第
个点,保证此时 。
许愿树不支持这些操作,现在小C希望你能帮助他加上这些功能。
输入格式
第一行一个正整数
第二行
如果
第三行一个正整数
接下来
如果
如果
如果
输出格式
输出若干行,每行一个整数表示询问的答案。
样例一
input
10 2 3 5 3 9 8 6 5 0 9 10 3 9 1 1 2 2 1 4 1 4 5 1 4 5 2 1 3 1 2 4 2 8 1 2 10 1 2 8 2
output
7 9 4 5 9 9
样例二至样例六
见样例数据下载。
限制与约定
本题采用捆绑测试,对于每个子任务,只有通过其中全部数据才可以获得分数。
对于全部数据,
特殊性质 0:保证数据随机。
特殊性质 1:保证所有修改都在询问之前。
特殊性质 2:保证每次一操作中的点
特殊性质 3:保证没有三操作
特殊性质 4:保证所有二操作中
特殊性质 5:保证没有二操作
测试点编号 | 特殊性质 | 分值 | |
---|---|---|---|
无 |
时间限制:
空间限制: