有许多类型的组合对象，其给定大小 $n$ 的不同对象数量为卡特兰数 $C_n = \frac{(2n)!}{n!(n+1)!}$。以下是前几个卡特兰数：$C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42, \dots$。考虑以下三种类型的对象：
周长为 $2n+2$ 的斜多格骨牌（Skew polyominoes）。它们是矩形板上的方格集合，板的大小为 $h \times w$，其中 $h+w = n+1$。多格骨牌必须是边连通的。左下角的方格和右上角的方格必须被多格骨牌占据。其他方格可以是空的或被占据，但必须满足以下条件：
- 在每一行和每一列中，被占据的方格形成一个连续的段；
- 每一列段的起始位置必须高于或等于其左侧邻居的起始位置；
- 每一列段的结束位置必须高于或等于其左侧邻居的结束位置；
- 每一行段的起始位置必须位于其下方邻居的右侧或同一位置；
- 每一行段的结束位置必须位于其下方邻居的右侧或同一位置。
长度为 $n$ 的 321-避免排列（321-avoiding permutations）。这些是元素为 $1, 2, \dots, n$ 的排列 $p_1, p_2, \dots, p_n$，其中不包含满足 $i < j < k$ 且 $p_i > p_j > p_k$ 的三元组位置。
凸 $(n+2)$-边形的三角剖分（Triangulations）。按遍历顺序将多边形的顶点标记为 $1$ 到 $n+2$ 的整数。在 $n$ 个三角形中的每一个里，将顶点编号按升序排列。然后，将三角形本身按整数三元组的升序排列。
固定数字 $n$ 并考虑三个集合： $A_n$，大小为 $n$ 的斜多格骨牌集合， $B_n$，大小为 $n$ 的 321-避免排列集合， * $C_n$，大小为 $n$ 的三角剖分集合。
构造这些集合之间的三射（trijection）。三射类似于双射，但涉及三个集合而不是两个。形式上，构造一个函数 $f_n : A_n \cup B_n \cup C_n \to A_n \cup B_n \cup C_n$，使得对于任何类型的对象，其函数值必然是另一种类型的对象，并且对于每个 $x$ 都有 $f_n(f_n(x)) = x$（换句话说，$f_n$ 是其自身的逆函数）。
在此之后，对于给定的三种类型的对象，打印三射的结果。 附加约束：给定的数字 $n$ 不能是 $2^k - 1$ 的形式。
交互
在本题中，你的程序在每个测试点上将运行两次。每一行输入均以换行符结束。
第一次运行
在第一次运行中，第一行包含两个空格分隔的整数 $n$ 和 $t$：大小（所有对象的大小相同）和对象数量（$2 \le n \le 35, 1 \le t \le 1000$，且 $n$ 不能是 $2^k - 1$ 的形式）。随后给出 $t$ 个对象。每个对象的描述以一行指示其类型的字符串开始，随后是一行或多行描述对象本身的内容，具体取决于类型。类型的详细描述和对象的格式规则如上文所述，并在下方的样例中展示。
在第一行，打印空格分隔的 $n$ 和 $t$（为了方便，这一行是格式的一部分，以便可以直接将程序的输出作为输入使用）。之后，打印 $t$ 个对象：即 $t$ 个给定对象的三射结果。对象的输出格式与输入格式相同。
第二次运行
在第二次运行中，输入和输出格式与第一次运行相同。然而，输入的不是 $t$ 个初始对象，而是第一次运行中打印出的对象，并经过随机重排。
$t$ 个初始对象在每个测试中是预先固定的。在第一次和第二次运行之间应用的随机排列也是预先固定的。
样例
对于每个测试，第二次运行的输入取决于第一次运行中程序的输出。下面展示了某个程序在第一个测试上的两次运行。注意第二次运行的输出是如何成为第一次运行的重排输入的。
样例输入 1
5 4 poly 4 2 .# ## ## #. perm 4 1 5 2 3 triang 1 2 4 1 4 5 1 5 7 2 3 4 5 6 7 perm 2 1 3 5 4
样例输出 1
5 4 perm 3 1 4 2 5 poly 4 2 ## ## ## #. poly 3 3 .## ### ##. triang 1 2 3 1 3 7 3 4 7 4 5 7 5 6 7
样例输入 2
5 4 poly 4 2 ## ## ## #. triang 1 2 3 1 3 7 3 4 7 4 5 7 5 6 7 poly 3 3 .## ### ##. perm 3 1 4 2 5
样例输出 2
5 4 perm 4 1 5 2 3 perm 2 1 3 5 4 triang 1 2 4 1 4 5 1 5 7 2 3 4 5 6 7 poly 4 2 .# ## ## #.