题目描述

翻译自 BalkanOI 2018 Day2 T1「Parentrises」

「括号串」是一个仅由 ( 和 ) 构成的字符串。如果在括号串中插入一些 $1$ 和 $+$ 可以将其转化为正确的表达式，该字符串就是一个「良括号串」。例如，(()) 和 ()() 是良括号串，而 )( 和 ( 不是。空字符串可视为良括号串。

将一个括号串（不要求是良括号串）的每个括号都涂成红 (R)、绿 (G)、蓝 (B) 三种颜色之一，如果有一种方案同时满足：

1. 忽略该串的所有蓝色括号后它是良括号串；
2. 忽略该串的所有红色括号后它是良括号串；

则该串就是 RGB 可读的。

你会接到两类任务之一。任务类型用一个整数 $P$ 表示，$P=1$ 或 $2$。

• $P=1$：你会接到 $T$ 组询问，每组询问包含一个括号串，试问该串是否 RGB 可读，如果是，请输出一种染色方案，如果否请输出 impossible；
• $P=2$：你会接到 $T$ 组询问，每组询问包含一个数 $N$，试求：有多少个长度为 $N$ 的 RGB 可读的良括号串。输出答案模 $10^9+7$ 的结果。

---

输入格式
第一行有一个整数 $P$。
第二行有一个整数 $T$。

如果 $P=1$，在接下来的 $T$ 行中，每行有一个括号串，表示询问。
如果 $P=2$，在接下来的 $T$ 行中，每行有一个数 $N$，表示询问。

---

输出格式
如果 $P=1$，对于每组询问，

• 如果该串是 RGB 可读的，请输出一种染色方案；
• 如果该串不是 RGB 可读的，请输出 impossible；

如果 $P=2$，对于每组询问，请输出长度为 $N$ 的 RGB 可读的良括号串的个数模 $10^9+7$ 的结果。

---

样例 1

输入

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

输出

GRBRBG
BBRBG
impossible

对于查询 $1$，忽略原串的所有蓝色括号后它变为 ()()；忽略原串的所有红色括号后它也变为 ()()。
对于查询 $2$，忽略原串的所有蓝色括号后它变为 ()；忽略原串的所有红色括号后它变为 ()()。

---

样例 2

输入

2
2
6
100

输出

12
959772055

---

数据范围与提示

$P = 1$：
设 $L$ 为字符串总长。

• 子任务 #1（$5$ 分）：$1 \le T \le 5$，$1 \le \text{len}(S) \le 13$。
• 子任务 #2（$11$ 分）：$1 \le L \le 100$。
• 子任务 #3（$6$ 分）：$1 \le L \le 1000$。
• 子任务 #4（$28$ 分）：$1 \le L \le 10^6$。

$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$。