巨斧砍大树

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

阿福最近练就了一个新的招式:巨斧砍大树。这个招式可以砍掉一颗二叉搜索树的某个子树。现在,阿福面前有一颗 $n$ 个结点的二叉搜索树,他要使用 $m$ 次招式,于是他想询问你每次使用「巨斧砍大树」后二叉搜索树会被砍成什么样子。

二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。

Input

第一行输入 $2$ 个整数 $n$, $m$ $(1 \leqslant n, m \leqslant 10)$。表示二叉搜索树的结点个数和招式使用次数。

第二行输入 $n$ 个空格隔开的整数 $v$ $(1 \leqslant v \leqslant 10)$,表示二叉搜索树是以此序列顺序插入生成的二叉树(保证互不相同)。

接下来输入 $m$ 行,每行一个整数 $w$ $(1 \leqslant w \leqslant 10)$,表示阿福要砍掉结点上数值为 $w$ 的子树(保证 $w$ 是初始二叉树上存在的数值)。

Output

对于每次砍树,如果成功砍掉子树,则先输出一行 Cut x,其中 $x$ 为被砍掉子树的根节点上的数值。如果要砍掉的结点在之前已被砍掉,则输出一行 Already cut x,$x$ 的含义同上。

随后输出一行,表示此次砍树结束后当前二叉树的中序遍历结果,以空格分隔(行末没有多余空格,如果整颗二叉树已为空,则输出一行空行)。

Sample Input

5 5
1 3 2 4 5
5
2
3
4
1

Sample Output

Cut 5
1 2 3 4
Cut 2
1 3 4
Cut 3
1
Already cut 4
1
Cut 1

Hint

Source

【2016级ACM暑假集训 结训赛(数据结构组)】bLue