题目描述

给定一棵n个结点的二叉搜索树，要求输出数值x的前驱和后继。 x的前驱定义为二叉树结点值中小于x的且最大的那个值。 x的后继定义为二叉树结点值中大于x的且最小的那个值。

输入格式

第一行是一个整数 n， 表示二叉树的结点个数。 二叉树结点编号从 1到 n（1<= n <= 10） ， 根结点为 1。 接下来有 n 行， 依次对应二叉树的 n 个结点。 每行有3个整数， 分别表示该结点的值、左儿子和右儿子的结点编号。 如果第2个（第3个） 数为-1 则表示没有左（右） 儿子。 最后一行一个整数 x。（数据保证输入的是二叉搜索树，x是其中的值）

输出格式

两行。第1行一个整数表示 x 在二叉搜索树中的前驱值。第1行一个整数表示 x 在二叉搜索树中的后继值。 如果x没有前驱或后继，输出"NON"。

样例

输入样例 1

7
13  2  6
3    3  4
2   -1 -1
5    5  -1
4   -1  -1
15 -1   7
17 -1  -1
4

输出样例 1

3
5

输入样例 2

7
13  2  6
3    3  4
2   -1 -1
5    5  -1
4   -1  -1
15 -1   7
17 -1  -1
2

输出样例 2

NON
3

输入样例 3

7
13  2  6
3    3  4
2   -1 -1
5    5  -1
4   -1  -1
15 -1   7
17 -1  -1
17

输出样例 3

15
NON

提示

提示：中序遍历二叉树，得到中序序列。在中序序列中找x和x的前驱和后继。