BST厂长 (bst.in/out/cpp)

时间限制: 1 s / 内存限制: 128 MB / 打开O2优化

题目描述

二叉树真是迷人......

随着时代的进步，二叉搜索树(Binary Search Tree)发挥着越来越大的作用。作为HNSDFZ上机部长XL，担负着为学校制造各种BST的任务。它们会用于各种用途：成绩排名、薪水发放、PY**......
本来学校对BST的需求并不是很大，但是自从ZY加入了上机组后，BST的需求越来越大......
作为XL，早已按捺不住。于是XL利用通用技术教学楼建立了一个厂房，专门制造各种BST。
这个厂子会收到各种各样的订单。每个订单都会是一个很长的数列，其中没有两个数是相同的。而XL要做的就是将这些数字依次插入到一棵空的BST中，然后将BST发送出去。
然而人工干这件事实在是太麻烦了，因此XL将ZY抓过来造BST。然而ZY更懒，把Link抓过来要它帮
ZY写个程序来构建BST。然而Link并不屑于写这个程序，于是这个任务莫名其妙地传到了你手上......
当然XL不会就这样放手不管，XL会随时来检查这棵BST是否是正确的，以防你在乱造BST。

输入格式

第一行输入一个正整数$n$，表示订单中数列的长度。
接下来$n$行，每行输入两个正整数$x$和$k$。表示将$x$插入到当前的BST中。初始时是空树。$k$则表示XL的检查。他会问你根节点到新插入的节点$x$的链上第$k$个节点是谁。默认从$1$开始数。

输出格式

对于每一次XL的检查，输出对应的答案。

样例输入

样例输出

1
2
3

2
2
3

提示及数据约定

对于第一次插入$2$，树的根节点为$2$，故答案为$2$。
对于第二次插入$1$，因为$1 \lt 2$，所以$1$是$2$的左儿子。$2$到$1$的链上的第一个节点为$2$
对于最后一次插入$3$，因为$3 \gt 2$，所以$3$是$2$的右儿子。$2$到$3$的链上的第二个节点是$3$。

对于$10\%$的数据，$n \le 20,000$。
对于$10\%$的数据，$n \le 90,000$。
对于$20\%$的数据，$n \le 100,000$。
对于另外$10\%$的数据，数列完全随机。
对于$100\%$的数据，$n \le 200,000$，$1 \le x \le n$，保证每次检查的节点存在。