C - Two Parentheses Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

配点：500 点

問題文

E869120 と square1001 は, 同じ長さの「正しい括弧列」を持っていました. 「正しい括弧列」とは、以下のような文字列を指す.

  • () は正しい括弧列である.
  • X が正しい括弧列であるとき, (, X、) をこの順につなげたものは正しい括弧列である.
  • X、Y が正しい括弧列であるとき, X と Y をこの順につなげたものは正しい括弧列である.
  • それ以外の括弧列は正しくない.

ここでは, E869120 の持つ括弧列を A, square1001 の持つ括弧列を B とする. chokudai は A, B に対して以下の操作を行った.

  • B の各文字について, ( であれば ), ) であれば ( に変えた. その後文字列 C (最初は空文字列) を定義し, 以下の 2 種類の操作のいずれかを A, B が両方空文字列となるまで繰り返した.
  • 文字列 C の末尾に A の先頭の一文字を挿入し, その後 A の先頭の一文字を削除する.
  • 文字列 C の末尾に B の先頭の一文字を挿入し, その後 B の先頭の一文字を削除する.

文字列 S が与えられる. S=C となる場合があり得るか, Yes か No か判定しなさい.

入力

入力は以下の形式で標準入力から与えられる. ただし, Q 回の質問に答えなければならないことに注意せよ. i 回目の質問における S は、ここでは S_i である. 

Q
S_1
S_2
 :
S_Q

出力

Q 行出力せよ.
i 行目には, i 回目の質問に対し, S=C となるような場合が存在するか, Yes か No を出力すること.

制約

  • Q は 1 以上 50 以下の整数.
  • S_i は 1 以上 20 \ 000 文字以内の (, ) から成る文字列.
  • S_i の長さは 4 の倍数である.

小課題

小課題 1 [90 点]

  • |S| \leq 16 を満たす.

小課題 2 [100 点]

  • |S| \leq 50 を満たす.

小課題 3 [310 点]

  • 追加の制約はない.

入力例 1

4
(())
)()(
(())
)(()

出力例 1

No
Yes
No
Yes

例えば, 2 回目の質問 (S_2) では, A = "()", B = ")(" であり, BAAB の順番で C に挿入すれば, C= )()( となる.
その場合, A, B, C は以下のように遷移する.

  • A = "()", B = ")(", C = ""
  • A = "()", B = "(", C = ")"
  • A = ")", B = "(", C = ")("
  • A = "", B = "(", C = ")()"
  • A = "", B = "", C = ")()("

入力例 2

1
(())(()(

出力例 2

No

このケースでは、( が 5 個, ) が 3 個存在する. 括弧列は ( と ) が同じ個数存在するので, これが S=C となることはあり得ない.

入力例 3

11
))(((()()())
))((())(())(
()())))(()((
)(()())()()(
)(())())(()(
)(()))()((()
)()()()())((
(())(()())()
)(())(()())(
((()())(()))
)))()())()()

出力例 3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No

配点：500 points

The string A and B should have same length, but it was not mentioned in the problem statement. We are very sorry for inconvenience.

Problem Statement

E869120 and square1001 have correct bracket sequences with same length. "Correct bracket sequence" is defined as follows:

  • () is a correct bracket sequence.
  • If X is a correct bracket sequence, the concatenation of (, X, ) in this order is also a correct bracket sequence.
  • If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.
  • Every correct bracket sequence can be derived from the rules above.

Let the bracket sequence of E869120 as A, and the bracket sequence of square1001 as B. chokudai performed the following operations from A and B.
Note that A and B should have equal length.

  • For each character of B, if it is (, he changed to ). If it is ), he changed to (. After this operation, he defined an empty string C, and he performed either of the two operations while A or B is non-empty string.
  • Insert the first character of A into the end of string C. After this, delete the first character of A.
  • Insert the first character of B into the end of string C. After this, delete the first character of B.

You are given a string S. Please check if it is possible to be S=C or not.

Input

Input is given from Standard Input in the following format. Note: You should answer Q queries. The string S in i-th query is S_i. 

Q
S_1
S_2
 :
S_Q

Output

Print Q lines.
In i-th line, print Yes if it is possible to be S_i = C, and print No if it is not possible to be S_i = C.

Constraints

  • 1 \leq Q \leq 50
  • 1 \leq |S_i| \leq 20 \ 000
  • S_i consists of ( and )
  • The length of S_i is divisible by 4.

Subtask

Subtask 1 [90 points]

  • |S| \leq 16.

Subtask 2 [100 points]

  • |S| \leq 50.

Subtask 3 [310 points]

  • There are no additional constraints.

Sample Input 1

4
(())
)()(
(())
)(()

Sample Output 1

No
Yes
No
Yes

In the 2nd query, if A is "()", B = "()" and chokudai did operations in order of BAAB, C should be )()(. In this case, A, B, C changes as follows:

  • A = "()", B = ")(", C = "" (After chokudai flips each character of B)
  • A = "()", B = "(", C = ")"
  • A = ")", B = "(", C = ")("
  • A = "", B = "(", C = ")()"
  • A = "", B = "", C = ")()("

Sample Input 2

1
(())(()(

Sample Output 2

No

In this case, there are 5 (s and 3 )s. Because the number of character ( and the number of character ) is the same for All correct bracket sequence, it is not possible to be S=C.

Sample Input 3

11
))(((()()())
))((())(())(
()())))(()((
)(()())()()(
)(())())(()(
)(()))()((()
)()()()())((
(())(()())()
)(())(()())(
((()())(()))
)))()())()()

Sample Output 3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No