题目描述

串可以按照字典序进行比较。例如：

abcd 小于 abdc

如果给定一个串，打乱组成它的字母，重新排列，可以得到许多不同的串，在这些不同的串中，有一个串刚好给定的串稍微大一些。科学地说：它是大于已知串的所有串中最小的串。你的任务就是求出这个“稍大的串”。

输入描述

第一行两个数 n,m (n,m≤10⁵) ，表示娃娃的数目以及 atm 想看的娃娃的数目。

接下来 n−1 行，每行两个数 u v，表示大小为 u 的娃娃里面套着一个大小为 v 的娃娃。保证 u>v 。

接下来 m 行，每行形如：

P x：表示 atm 一定要看到大小为 x 的娃娃；

Q x ：表示 atm 只想知道为了看大小为 x 的娃娃，他需要打开多少个娃娃，但实际上并不打开他们。

输出描述

输出 m 行。对应输入中 P 操作或 Q 操作需要打开（或假想打开）多少个俄罗斯娃娃。

输入输出样例

示例 1

输入

abfxy

输出

abfyx

示例 2

输入

ayyyxxff

输出

fafxxyyy

数据规模约定：

输入的串不超过1000个字符。

特例：

如果已知的串已经是所有重组串中最大的，则原样输出读入的那个串。