시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB222100.000%

## 문제

Let us define the set of regular bracket-and-bar sequences $R$ recursively. It is the set of strings that can be obtained following only the rules below:

• $\varepsilon \in R$ (empty string)
• $A, B \in R \Rightarrow AB \in R$ (concatenation)
• $A, B \in R \Rightarrow$($A$|$B$)$\in R$

For example, the sequences containing two triples "(|)" look as folows: "((|)|)", "(|(|))", "(|)(|)".

Establish a correspondence between regular bracket-and-bar sequences of certain length and integers, and implement that correspondence.

## 인터랙션

In this problem, your solution will be run twice on each test. Each line of input is terminated by an end-of-line character.

## 첫 번째 실행

During the first run, the solution encodes bracket-and-bar sequences as integers. The first line contains the word "encode". The second line contains an integer $t$: the number of test cases ($1 \le t \le 1000$). Each test case is given on two lines: the first line contains an integer $n$ which is the number of "(|)" triples in the sequence ($1 \le n \le 25$), and the second line contains $3 n$ characters without spaces, constituting a reqular bracket-and-bar sequence with $n$ triples.

Print $t$ lines, one for each test case. On the $i$-th line, print an integer $x_i$ which you chose to encode the $i$-th sequence from the input ($0 \le x_i \le 2 \cdot 10^{18}$).

## 두 번째 실행

During the second run, the solution decodes bracket-and-bar sequences from integers. The first line contains the word "decode". The second line contains an integer $t$: the number of test cases ($1 \le t \le 1000$). Each test case is given on two lines: the first line contains an integer $n$ which is the number of "(|)" triples in the sequence ($1 \le n \le 25$), and the second line contains the integer printed by your solution for this test case during the first run.

Print $t$ lines, one for each test case. On the $i$-th line, print the bracket-and-bar sequence from the $i$-th test case.

## 예제

For each test, the input during the second run depends on the solution's output during the first run.

Below we show two runs of a certain solution on the first test. It can be seen that this solution encodes the characters by digits $1$, $2$, and $3$, and just prints the resulting string of digits as the encoding integer. Unfortunately, for large $n$, the strings will become too long.

## 예제 입력 1

encode
3
1
(|)
4
((((|)|)|)|)
5
(|(|))((|(|))|)


## 예제 출력 1

123
111123232323
121233112123323


## 예제 입력 2

decode
3
1
123
4
111123232323
5
121233112123323


## 예제 출력 2

(|)
((((|)|)|)|)
(|(|))((|(|))|)


## 채점 및 기타 정보

• 예제는 채점하지 않는다.