Problem Description

Translated from BalkanOI 2018 Day2 T1 "Parentrises"

A "parenthesis string" is a string consisting only of ( and ). If a parenthesis string can be turned into a valid expression by inserting some 1s and +s, it is called a "well-formed parenthesis string". For example, (()) and (()) are well-formed parenthesis strings, while )( and ( are not. An empty string is considered a well-formed parenthesis string. (This is the same as the Catalan number you learned about.)

A parenthesis string (which is not well-formed) can be colored in one of three colors: red, green, or blue. If there is a coloring scheme that satisfies both:
+ Ignoring all blue parentheses, the string becomes a well-formed parenthesis string;
+ Ignoring all red parentheses, the string becomes a well-formed parenthesis string;

then the string is RGB readable.

You will receive one of two types of tasks, indicated by an integer $P$, where $P=1$ or $2$.

• $P=1$: You will receive $T$ queries, each containing a parenthesis string. Determine if the string is RGB readable. If it is, output a coloring scheme. If not, output impossible.
• $P=2$: You will receive $T$ queries, each containing a number $N$. Determine the number of well-formed parenthesis strings of length $N$ that are RGB readable. Output the answer modulo $(10^9+7)$.

Input Format

The first line contains an integer $P$.
The second line contains an integer $T$.
+ If $P=1$, the next $T$ lines each contain a parenthesis string representing the query.
+ If $P=2$, the next $T$ lines each contain a number $N$ representing the query.

Output Format

If $P=1$, for each query:
+ If the string is RGB readable, output a coloring scheme.
+ If the string is not RGB readable, output impossible.

If $P=2$, for each query, output the number of well-formed parenthesis strings of length $N$ that are RGB readable, modulo $(10^9+7)$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

GRBRBG
BBRBG
impossible

Sample Input #2

2
2
6
100

Sample Output #2

12
959772055

Notes

Sample 1 Explanation:

For query 1, ignoring all blue parentheses results in ()(), and ignoring all red parentheses also results in ()().
For query 2, ignoring all blue parentheses results in (), and ignoring all red parentheses results in ()().

$P = 1$:
Let $L$ be the total length of the strings.
Subtask #1 (5 points): $1 ≤ T ≤ 5$, $1 ≤ len(S) ≤ 13$.
Subtask #2 (11 points): $1 ≤ L ≤ 100$.
Subtask #3 (6 points): $1 ≤ L ≤ 1000$.
Subtask #4 (28 points): $1 ≤ L ≤ 10^6$.

$P = 2$:
* Subtask #5 (6 points): $1 ≤ N, T ≤ 15$.
Subtask #6 (16 points): $1 ≤ N, T ≤ 30$.
Subtask #7 (28 points): $1 ≤ N, T ≤ 300$.

Thanks to Planet6174 for the translation.

见题面 Input 部分

见题面 Output 部分