시간 제한메모리 제한제출정답맞힌 사람정답 비율
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

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

채점 및 기타 정보

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