問題文

(, ) のみからなる文字列のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。

• 空文字列
• ある「正しい括弧列」A が存在して (, A, ) をこの順につなげた文字列
• ある空でない「正しい括弧列」A,\ B が存在して A,\ B をこの順につなげた文字列

長さ 4N で (, ) のみからなる文字列 S と 2N 個の 2 整数の組 (L_i, R_i)\ (1\leq L_i < R_i \leq 4N) が与えられます。ここで、(L_1,L_2,\dots,L_{2N}) は (1,2,\dots,2N) の、(R_1,R_2,\dots,R_{2N}) は (2N+1,2N+2,\dots,4N) の順列です。

i=1, 2,\dots,2N の順に S の L_i,\ R_i 文字目のいずれかに印をつけた後、印をつけた文字のみを左から順に読み、長さ 2N の文字列として解釈したものを S' とします。

S' を「正しい括弧列」にできるか判定してください。

T 個のテストケースについて答えてください。

制約

• 入力される数値はすべて整数
• 1 \leq T \leq 1000
• 1 \leq N \leq 2000
• S は (, ) のみからなる長さ 4N の文字列
• 1 \leq L_i \leq 2N < R_i \leq 4N
• (L_1,L_2,\dots,L_{2N}) は (1,2,\dots,2N) の順列
• (R_1,R_2,\dots,R_{2N}) は (2N+1,2N+2,\dots,4N) の順列
• 1 つの入力に含まれるテストケースについて、 N の総和は 2000 以下

入力例 1

3
1
()()
1 3
2 4
2
))()((()
1 6
2 5
3 7
4 8
8
))()))))()())((((()))(()(()))(((
8 26
2 25
1 18
4 22
7 17
12 32
10 31
5 30
15 27
9 23
13 19
11 24
14 29
6 28
16 20
3 21

出力例 1

Yes
No
Yes

1 番目のテストケースについて、 L_1=1 文字目と R_2=4 文字目に印をつけると S' は () となり、これは「正しい括弧列」です。

2 番目のテストケースについて、どのように印をつけても S' は「正しい括弧列」になりません。