RGB Readable Parenthesis Strings

This problem is adapted from BalkanOI 2018 Day 2 T1 Parentrises.

A bracket string is a string consisting solely of the characters '(' and ')'. A bracket string is called a good parenthesis string if by inserting some 1's and + signs into the string it can be transformed into a valid expression. (This is the same concept as the well‐known Catalan numbers problem.) For example, both (()) and ()() are good parenthesis strings, while )( and ( are not. The empty string is considered good.

Now, consider coloring every bracket in a given bracket string (which is not necessarily good) with one of three colors: red, green or blue. We call the colored string RGB readable if there exists a coloring scheme such that:

• If you remove all blue brackets, the resulting sequence is a good parenthesis string.
• If you remove all red brackets, the resulting sequence is a good parenthesis string.

You will be given one of the following two types of tasks, indicated by an integer P (which will be either 1 or 2):

• P = 1: You are given T test cases. In each test case you are provided with a bracket string. Determine if the string is RGB readable. If it is, output one valid coloring scheme as a string consisting of the letters 'R', 'G' and 'B', where the i-th character denotes the color assigned to the i-th bracket; otherwise, output impossible.
• P = 2: You are given T test cases. In each test case you are provided with an integer N. Count the number of good parenthesis strings of length N that are RGB readable. Since N must be even for a bracket string to be good, if N is odd the answer is 0. Otherwise, every good parenthesis string is RGB readable (by choosing all brackets to be green), so the answer is the n-th Catalan number (with n = N/2). Output your answer modulo 10^9+7.

Note: A valid parenthesis string is one in which parentheses match correctly. For any parenthesis string, a straightforward greedy check that increases a counter for '(' and decreases for ')' (never allowing the counter to go negative and requiring that the counter is 0 at the end) can confirm its validity.

inputFormat

The first line of input contains an integer P (either 1 or 2) indicating the type of task.

If P = 1, the next line contains an integer T, the number of test cases. Each of the following T lines contains a non-empty bracket string consisting only of the characters '(' and ')'.

If P = 2, the next line contains an integer T. Each of the following T lines contains an integer N, representing the length of the bracket string.

outputFormat

If P = 1, for each test case output a line containing either a valid coloring scheme (a string of the same length as the input string consisting of the letters 'R', 'G', and 'B') if the bracket string is RGB readable, or the word impossible if no such coloring exists.

If P = 2, for each test case output a line containing a single integer: the number of RGB readable good parenthesis strings of length N, taken modulo 10^9+7.

sample

1
2
)(
()()

impossible
GGGG