我们递归地定义正则括号与竖线序列集合 $R$。它是可以通过以下规则获得的字符串集合：

• $\varepsilon \in R$（空字符串）
• $A, B \in R \Rightarrow AB \in R$（连接）
• $A, B \in R \Rightarrow (A|B) \in R$

例如，包含两个三元组 “(|)” 的序列如下所示：“((|)|)”、“(|(|))”、“(|)(|)”。

请建立特定长度的正则括号与竖线序列与整数之间的对应关系，并实现该对应关系。

交互

在本题中，你的程序将在每个测试点上运行两次。每一行输入均以换行符结束。

第一次运行

在第一次运行中，程序将括号与竖线序列编码为整数。第一行包含单词 “encode”。第二行包含一个整数 $t$：测试用例的数量 ($1 \le t \le 1000$)。每个测试用例占两行：第一行包含一个整数 $n$，表示序列中 “(|)” 三元组的数量 ($1 \le n \le 25$)；第二行包含 $3n$ 个不含空格的字符，构成一个包含 $n$ 个三元组的正则括号与竖线序列。

请输出 $t$ 行，每行对应一个测试用例。在第 $i$ 行，输出你选择用于编码输入中第 $i$ 个序列的整数 $x_i$ ($0 \le x_i \le 2 \cdot 10^{18}$)。

第二次运行

在第二次运行中，程序将整数解码为括号与竖线序列。第一行包含单词 “decode”。第二行包含一个整数 $t$：测试用例的数量 ($1 \le t \le 1000$)。每个测试用例占两行：第一行包含一个整数 $n$，表示序列中 “(|)” 三元组的数量 ($1 \le n \le 25$)；第二行包含你在第一次运行中为该测试用例输出的整数。

请输出 $t$ 行，每行对应一个测试用例。在第 $i$ 行，输出第 $i$ 个测试用例对应的括号与竖线序列。

样例

输入格式 1

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

输出格式 1

123
111123232323
121233112123323

输入格式 2

decode
3
1
123
4
111123232323
5
121233112123323

输出格式 2

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

说明

对于每个测试，第二次运行的输入取决于第一次运行中程序的输出。上面展示了某个程序在第一个测试上的两次运行。可以看出，该程序将字符编码为数字 1、2 和 3，并直接将得到的数字字符串作为编码后的整数输出。遗憾的是，对于较大的 $n$，字符串会变得过长。