AT_utpc2022_i Which must be deleted?

`(`, `)` のみからなる文字列のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。 - 空文字列 - ある「正しい括弧列」 $ 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 $ 個のテストケースについて答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ N $ $ S $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_{2N} $ $ R_{2N} $

$ T $ 行出力せよ。 $ i\ (1\leq i \leq T) $ 行目には $ i $ 番目のテストケースについて、 $ S' $ を「正しい括弧列」にできる場合は `Yes` を、できない場合は `No` を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて、 $ L_1=1 $ 文字目と $ R_2=4 $ 文字目に印をつけると $ S' $ は `()` となり、これは「正しい括弧列」です。 $ 2 $ 番目のテストケースについて、どのように印をつけても $ S' $ は「正しい括弧列」になりません。 ### Constraints - 入力される数値はすべて整数 - $ 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 $ 以下