题目描述

$N$ 头牛，编号为 $1\sim N$，正在与 Farmer John 玩一个疯狂的游戏。奶牛会排成一行（牛线），问 Farmer John 此时的行号是多少。之后，Farmer John 会给牛一个行号，牛必须按照新行号排列成线。

行号是通过以字典序对行的所有排列进行编号来分配的。比如说：Farmer John 有 $5$ 头牛，让他们排为行号 $3$，排列顺序为：

$1$st: $\texttt{1 2 3 4 5}$

$2$nd: $\texttt{1 2 3 5 4}$

$3$rd: $\texttt{1 2 4 3 5}$

因此，牛将在牛线 $\texttt{1 2 4 3 5}$ 中。

之后，奶牛排列为 $\texttt{1 2 4 3 5}$，并向 Farmer John 问他们的行号。继续列表：

$4$th: $\texttt{1 2 4 5 3}$

$5$th: $\texttt{1 2 5 3 4}$

Farmer John 可以看到这里的答案是 $5$。

Farmer John 和奶牛希望你的帮助玩他们的游戏。他们需要 $K$ 组查询，查询有两个部分：$C_i$将是 P 或 Q 的命令。

• 如果 $C_i$ 是 P，则查询的第二部分将是一个整数 $A_i$，它是行号。此时，你需要回答正确的牛线。

• 如果 $C_i$是 Q，则查询的第二部分将是 $N$ 个不同的整数 $B_{i,j}$。这将表示一条牛线，此时你需要输出正确的行号。

输入格式

第 $1$ 行两个整数 $N,K$。

第 $2\sim 2K+1$ 行：第 $2i$ 行，一个字符 P 或 Q，指明类型。

如果第 $2i$ 行是 P，则第 $2i+1$ 行是一个整数，表示行号；如果第 $2i$ 是 Q，则第 $2i+1$ 行是 $N$ 个空格隔开的整数，表示牛的排列方式。

输出格式

第 $1\sim K$ 行：如果输入的第 $2i$ 行是 P，则输出牛的排列方式；如果输入的第 $2i$ 行是 Q，则输出行号。

5 2
P
3
Q
1 2 5 3 4

1 2 4 3 5
5

数据规模与约定

对于 $100\%$ 的数据，$1\leq N\leq 20$，$1\leq K\leq 10^4$，$1\leq A_i\leq N!$，$1\leq B_{i,j}\leq N$。

题目来源

Silver