在本题中，你需要构造一个双射，将每个长度为 $n$ 且包含 $k$ 个循环的排列映射为一个长度为 $n$ 且包含 $k$ 个记录的排列。

长度为 $n$ 的排列 $p$ 是一个包含 $n$ 个整数 $p(1), p(2), \dots, p(n)$ 的序列，其中 $1, 2, \dots, n$ 中的每个数字恰好出现一次。

排列 $p$ 中的一个循环是一个整数序列 $c_1, c_2, \dots, c_m$，满足 $p(c_1) = c_2, p(c_2) = c_3, \dots, p(c_m) = c_1$。一个特殊情况是长度为 1 的循环：$p(i) = i$。可以证明，每个排列都可以表示为一组两两不相交的循环。

排列 $p$ 中的一个记录（或记录值）是指其元素 $p_j$，它大于该排列中排在它前面的所有元素：对于所有 $i < j$，都有 $p_j > p_i$。注意，根据定义，$p_1$ 始终是一个记录。

可以证明，对于任意给定的 $n$ 和 $k$，长度为 $n$ 且恰好包含 $k$ 个循环的排列数量等于长度为 $n$ 且恰好包含 $k$ 个记录的排列数量。因此，存在一个双射，将长度为 $n$ 且包含 $k$ 个循环的排列映射到长度为 $n$ 且包含 $k$ 个记录的排列，反之亦然。回想一下，双射是一种给出两个集合元素之间精确配对的函数：第一个集合中的每个元素与第二个集合中的恰好一个元素配对，且第二个集合中的每个元素也与第一个集合中的恰好一个元素配对。你的任务是找到并实现这样一个函数。

输入格式

输入的第一行包含一个整数 $t$，表示排列的数量 ($1 \le t \le 300\,000$)。

接下来的 $t$ 行，每行包含一个排列的描述。描述以一个整数 $n$ 开头，表示排列的长度 ($1 \le n \le 300\,000$)，随后是一个字符，即 “r” 或 “c”，表示排列的类型。接着是一个包含 $n$ 个整数的序列，构成了排列本身。$1$ 到 $n$ 之间的每个整数在该序列中恰好出现一次。

行内的连续标记由单个空格分隔。输入中所有排列的总长度不超过 $300\,000$。

输出格式

输出必须与输入格式相同。

输出的第一行必须包含整数 $t$，即输入中排列的数量。

此后，对于给定的 $t$ 个排列中的每一个，在单独的一行上输出对应的排列。如果输入排列的类型为 “r”，则找出其中的记录数，并输出一个具有相同循环数的 “c” 类型排列。如果输入排列的类型为 “c”，则找出其中的循环数，并输出一个具有相同记录数的 “r” 类型排列。

$t$ 行中的每一行必须以整数 $n$ 开头，即排列的长度，后跟表示类型的字符。之后必须跟随构成排列本身的 $n$ 个整数。行内的连续标记由单个空格分隔。

对应关系必须是一致的：如果一个 “r” 类型的排列 $p$ 对应一个 “c” 类型的排列 $q$，则逆对应关系也必须成立，即没有其他 “c” 类型的排列对应于 $p$，也没有其他 “r” 类型的排列对应于 $q$。但请注意，你的双射不需要在不同的输出之间保持一致。

样例

样例输入 1

6
3 r 1 2 3
3 c 1 2 3
3 r 2 1 3
3 r 2 3 1
3 c 2 1 3
2 c 2 1

样例输出 1

6
3 c 1 2 3
3 r 1 2 3
3 c 2 1 3
3 c 3 2 1
3 r 2 1 3
2 r 2 1

说明

在本例中，前五个排列的长度均为 $n = 3$。第一个排列类型为 “r”，包含三个记录。第二个排列类型为 “c”，包含三个循环。这两个排列相互对应。第三个和第四个排列类型为 “r”，每个包含两个记录。第五个排列类型为 “c”，包含两个循环。它对应于第三个排列。第四个排列对应于类型为 “c” 的排列 3, 2, 1，这是另一个包含两个循环的排列。

最后一个排列长度为 $n = 2$，类型为 “c”，包含一个循环。它对应于类型为 “r” 的排列 2, 1，该排列包含一个记录。

注意，这并不是唯一的双射：上面给出了另一种可能的输出。在这里，对于输入中的第三个排列（类型为 “r” 的 2, 1, 3），我们选择类型为 “c” 的 3, 2, 1 作为对应的排列。然后，第四个排列（类型为 “r” 的 2, 3, 1）也必须得到一个不同的对应排列，我们取类型为 “c” 的 1, 3, 2。此后，对于第五个排列（类型为 “c” 的 2, 1, 3），唯一的选择是选取类型为 “r” 的 1, 3, 2，因为其他两个包含两个记录的排列已经对应了不同的包含两个循环的排列。