Problem J: いにしえの数式

あなたの友人の考古学者が遺跡を発掘していた． ある日，彼は怪しげな記号の羅列が刻まれている石盤を大量に発見した． 彼はこの大発見に大喜びし，すぐさま石盤に刻まれている記号の解読を始めた． 何週間にもわたる彼の解読の努力の結果， どうやらこれらの石盤には変数・演算子・カッコの組み合わせで成り立っている 数式のようなものが刻まれていることがわかった． 発掘した石盤と遺跡に関わる文献を調べていくうちに彼はさらに， それぞれの石盤で演算子の結合規則が異なっており， それぞれの石盤の先頭に演算子の結合規則が記されているらしいことを突きとめた． しかし，彼は数学が苦手であるため，演算子の結合規則を見ても すぐには数式がどのように結合しているかがわからなかった． そこで彼は，優れたコンピュータサイエンティストであるあなたに 「石盤に書かれている数式がどのように結合しているかを調べてほしい」 と依頼してきた． あなたは，彼を手助けすることができるだろうか？

数式中に現れる演算子には優先順位が定められており， 優先順位の高い演算子から順に結合していく． 同一優先順位をもつ演算子にはそれぞれ結合方向が定められており， 左から右に結合する場合は左にある演算子から順に， 右から左に結合する場合は右にある演算子から順に結合していく． 例えば， + より * の方が優先順位が高く， * が左から右に結合する場合， 式 a+b*c*d は (a+((b*c)*d)) のように結合する． サンプル入力にも他の例がいくつか挙げられているので参照のこと．

Input

入力に与えられる数式は，以下の Expr で定義されるような文字列である． この定義において，Var は変数を表し， Op は演算子を表す．

Expr ::= Var
| Expr Op Expr
| “(” Expr “)”
Var ::= “a” | “b” | ... | “z”
Op ::= “+” | “-” | “*” | “/” | “<” | “>” | “=” | “&” | “|” | “^”

演算子はすべて二項演算子であり，単項演算子やその他の演算子は存在しない．

入力は，いくつかのデータセットからなる． 入力の先頭行にデータセット数 D (D ≤ 100) が与えられ， 以降の行に D 個のデータセットが続く．

それぞれのデータセットは，次のようなフォーマットで与えられる．

（演算子の結合規則の定義）
（クエリの定義）

演算子の結合規則の定義は，以下のようなフォーマットで与えられる．この定義において，G は演算子グループの数を表す数である．

G
（演算子グループ1 の定義）
（演算子グループ2 の定義）
...
（演算子グループG の定義）

演算子は，結合の優先順位ごとにグループに分けられている． 同一のグループに属する演算子は結合の優先順位が等しく， グループの定義が後に現れる演算子の方が 前に現れる演算子より結合の優先順位が高い．

それぞれの演算子グループは，以下のように定義される．

A M p1 p2 ... pM

A は演算子の結合方向を表す文字で， “L” か “R” の いずれかである． “L” は左から右に結合することを表し， “R” は右から左に結合することを表す． M (M > 0) は演算子グループに含まれる演算子の数であり， pi (1 ≤ i ≤ M) はグループに含まれる演算子を表す文字である． 同じ演算子がグループ内に2度現れることはなく，また， データセット内にグループをまたがって 同じ演算子が2度現れることもない．

演算子の定義には，上記の Op で定義された演算子のみが現れる． 1つのデータセットにおいて，必ず1つ以上の演算子が定義されると仮定してよい．

クエリの定義は以下のようなフォーマットで与えられる．

N
e1
e2
...
eN

N (0 < N ≤ 50) はクエリとして与えられる 数式の数である． ei (1 ≤ i ≤ N) は上記の Expr の定義を満たすような 式を表す空でない文字列である． ei の長さはたかだか100文字であり， 当該データセットで定義されていない演算子は出現しないものと仮定してよい．

Output

データセットごとに， クエリとして与えられたそれぞれの式について， 式中の各演算子について必ず1つのカッコの組を用いて すべての二項演算を正しく囲み， 演算子の結合を表現した文字列を出力せよ． 入力の式に現れる変数や演算子の順序を変更してはならない．

それぞれのデータセットの間には空行を出力せよ． 出力の末尾に空行を出力してはならない．

Sample Input

2
3
R 1 =
L 2 + -
L 2 * /
6
a+b*c-d
(p-q)/q/d
a+b*c=d-e
t+t+t+t+t
s=s=s=s=s
(((((z)))))
3
R 3 = < >
L 3 & | ^
L 4 + - * /
1
a>b*c=d<e|f+g^h&i<j>k

Output for the Sample Input

((a+(b*c))-d)
(((p-q)/q)/d)
((a+(b*c))=(d-e))
((((t+t)+t)+t)+t)
(s=(s=(s=(s=s))))
z

(a>((b*c)=(d<((((e|(f+g))^h)&i)<(j>k)))))