Description

编号为 $1$ 到 $N (1 \leq N \leq 20)$ 的 $N$ 头奶牛正在和农夫约翰玩他们的又一个疯狂游戏。奶牛们将自己排列成一行，并询问农夫约翰它们的排列编号是多少。作为回应，农夫约翰可以给它们一个排列编号，奶牛们必须重新排列成那个排列。

排列编号是通过按字典序给所有排列编号来分配的。

考虑这个例子：

农夫约翰有 $5$ 头奶牛，并给它们排列编号 $3$ 。

按升序字典序排列的排列：第 $1$ 个：$1,2,3,4,5$

第 $2$ 个：$1,2,3,5,4$

第 $3$ 个：$1,2,4,3,5$

因此，奶牛们将自己排列成奶牛排列 $1,2,4,3,5$。

奶牛们反过来排列成配置「$1,2,5,3,4$」，并询问农夫约翰它们的排列编号是多少。

继续列表：

第 $4$ 个：$1,2,4,5,3$

第 $5$ 个：$1,2,5,3,4$

农夫约翰可以看到答案是 $5$ 。

农夫约翰和奶牛们希望你能帮助他们玩这个游戏。他们有 $K (1 \leq K \leq 10,000)$ 个查询需要帮助。查询 $i$ 有两个部分：$C_i$ 是命令，可以是 P 或 Q 。

如果 $C_i$ 是 P ，那么查询的第二部分将是一个整数 $A_i (1 \leq A_i \leq N!)$，这是一个排列编号。这是农夫约翰挑战奶牛们排成正确的奶牛排列。

如果 $C_i$ 是 Q，那么查询的第二部分将是 $N$ 个不同的整数 $B_{ij} (1 \leq B_{ij} \leq N)$。这将表示一个奶牛排列。这是奶牛们挑战农夫约翰找出它们的排列编号。

Input Format

* 第 $1$ 行：两个用空格分隔的整数：$N$ 和 $K$

* 第 $2$ 行到第 $2 \times K + 1$ 行：第 $2 \times i$ 行和第 $2 \times i + 1$ 行将包含一个查询。

第 $2 \times i$ 行将只包含一个字符：如果奶牛们排列并询问农夫约翰它们的排列编号，则为 Q；如果农夫约翰给奶牛们一个排列编号，则为 P。

如果第 $2 \times i$ 行是 Q，那么第 $2 \times i + 1$ 行将包含 $N$ 个用空格分隔的整数 $B_ij$，表示奶牛排列。如果第 $2 \times i$ 行是 P，那么第 $2 \times i + 1$ 行将包含一个整数 $A_i$，这是要解决的排列编号。

Output Format

* 第 $1$ 行到第 $K$ 行：第 $i$ 行将包含查询 $i$ 的答案。

如果输入的第 $2 \times i$ 行是 Q，那么这一行将包含一个整数，即第 $2 \times i + 1$ 行中奶牛排列的排列编号。

如果输入的第 $2 \times i$ 行是 P，那么这一行将包含 $N$ 个用空格分隔的整数，给出第 $2 \times i + 1$ 行中编号的奶牛排列。

5 2 
P 
3 
Q 
1 2 5 3 4 

1 2 4 3 5 
5 

Hint

（由 ChatGPT 4o 翻译）