我们将字符串定义为由字符 ‘(‘ 和 ‘)’ 组成的序列。

我们将“合法括号序列”定义为可以通过在字符之间插入 ‘1’ 和 ‘+’ 从而转化为正确算术表达式的字符串。例如，字符串 "()()" 和 "(())" 是合法的，它们可能的表达式分别为 "(1)+(1)" 和 "((1+1)+1)"，而 ")(" 和 "(" 则不是。空字符串被定义为合法括号序列。

Bogdan Shepherd 和 Rolling Costel 在 B.U.A.P.（不必要算法问题局）的无用括号部门工作。他们通常会收到两类任务：

1. Theo of Fire 和 Radu the Mountain（他们的客户）都是色盲，他们有一个字符串 $S$。Theo 只能看到红色和绿色，而 Radu 只能看到蓝色和绿色。他们想要对 $S$ 进行染色，使得如果他们各自忽略掉自己看不到颜色的括号，两人看到的都是合法括号序列。染色仅能使用红、绿、蓝三种颜色。如果存在这样的染色方案，我们称 $S$ 是 RGB-可读的。请找出一个可能的染色方案，或者报告不存在。
2. Mihai Likelance 和 Andrei the Priest（其他客户）想要知道对于给定的 $N$，长度为 $N$ 的不同 RGB-可读字符串的数量。他们希望得到模 $1.000.000.007$ 的答案。

输入格式

第一行包含一个整数 $P$，表示你需要解决的问题类型： 如果 $P = 1$，你将解决 Theo 和 Radu 的请求。 如果 $P = 2$，你将解决 Mihai 和 Andrei 的请求。

第二行包含一个整数 $T$，表示文件中的测试用例数量。 接下来的 $T$ 行，每行包含一个测试用例： 如果 $P = 1$，你将收到一个字符串 $S$。 如果 $P = 2$，你将收到一个数字 $N$。

输出格式

对于每个测试用例，在单独的一行中输出答案。 如果 $P = 1$ 且无解，输出 "impossible"（引号仅为清晰起见）。 如果 $P = 1$ 且有解，输出一个可能的染色方案。行中的第 $i$ 个字符应表示 $S$ 中第 $i$ 个字符的颜色，用 ‘R’ 表示红色，‘B’ 表示蓝色，‘G’ 表示绿色。 如果 $P = 2$，输出答案模 $1.000.000.007$ 的结果。

子任务

对于 $P = 1$： 令 $L$ 为输入文件中字符串的总字符数，则： 子任务 1 (5 分)：$1 \le T \le 5$，$1 \le \text{length of } S \le 13$ 子任务 2 (11 分)：$1 \le L \le 100$ 子任务 3 (6 分)：$1 \le L \le 1.000$ 子任务 4 (28 分)：$1 \le L \le 1.000.000$

对于 $P = 2$： 子任务 5 (6 分)：$1 \le N, T \le 15$ 子任务 6 (16 分)：$1 \le N, T \le 30$ * 子任务 7 (28 分)：$1 \le N, T \le 300$

样例

样例输入 1

1
3
())(()
()(()
()))

样例输出 1

GRBRBG
BBRBG
impossible

说明 1

在第一个例子中，Theo 和 Radu 看到的都是字符串 "()()"。 在第二个例子中，Theo 看到的字符串是 "()"，Radu 看到的字符串是 "()()"。 在第三个例子中，不存在有效的染色方案。

样例输入 2

2
2
6
100

样例输出 2

12
959772055