Description

小任是个神人，因为他在猜测杯子颜色方面可以做到出类拔萃。

现在小朱把 $6$ 个不同颜色的杯子排成一排（第一个杯子的位置为 $0$），每个杯子的颜色是红色，橙色，黄色，绿色，蓝色，紫色中的一种（致敬传奇北大队伍赤橙黄绿蓝紫）。但是杯子被一块布盖住了，我们并不知道每个杯子是什么颜色。给出一个长度为 $6$ 的字符串由小写英文字母组成，表示小任猜测每个杯子的颜色。其中$r$ 表示红色，$o$ 表示橙色，$y$ 表示黄色，$g$ 表示绿色，$b$ 表示蓝色，$p$ 表示紫色。

但是你对小任猜测的结果始终持怀疑态度，为了解决这个问题，小朱会执行 $q$ 次以下操作： 选取两个位置 $x,\ y$,并交换 $x$ 和 $y$ 位置上的杯子，如果 $x=y$，表示什么都没有操作。最后小朱会告诉你现在有 $z$ 个杯子和小任猜的一样。每次交换完，并不会把杯子换回去，也就是说每次操作后杯子的状态都会继承到下一次操作。

为了击碎小任的谎言，请你输出所有可能满足条件的颜色分配数量，并按字典序从小到大输出最初所有可能的杯子的颜色排列。

颜色排列由一个长度为 $6$ 的字符串表示，$r$ 表示红色，$o$ 表示橙色，$y$ 表示黄色，$g$ 表示绿色，$b$ 表示蓝色，$p$ 表示紫色。

长度相同时，字符串 $s$ 的第一个不同的字符比字符串 $t$ 第一个不同的字符大，则 $s$ 的字典序比 $t$ 大。

例如：$"abs"$ 和 $"aba"$ 第一个不同的字符分别是 $'s'$ 和 $'a'$，因为 $'s'$ > $'a'$，所以 $"abs"$ 的字典序更大。

Format

Input

第一行有一个长度为 $6$ 的字符串，表示小任猜测的每个杯子的颜色。

第二行有一个整数 $q$，表示小朱给出的操作数，其中 $1\leq q \leq 5000$。

接下来 $q$ 行，每行有三个整数 $x,y,z$，表示交换 $x$ 位置和 $y$ 位置上的杯子后，一共有 $z$ 个杯子的颜色和小任的猜测的相同，其中 $0\leq x,y\leq 5$，$0\leq z\leq 6$。

Output

第一行输出一个整数 $n$，表示可能的颜色排列数量。

接下来 $n$ 行按字典序输出表示颜色排列的字符串。

Samples

roygbp
3
1 3 1
2 3 2
5 0 4

4
pbgoyr
pogybr
pybogr
pyogbr

Limitation

1s, 1024KiB for each test case.