D - (xx) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

(, x, ) からなる文字列 A が与えられます。
あなたは A に対して次の 2 種類の操作を自由な順番で自由な回数行うことが出来ます。

  • A の部分文字列 (xx) を 1 カ所選び、xx に置換する。
  • A の部分文字列 xx を 1 カ所選び、(xx) に置換する。

(, x, ) からなる文字列 B が与えられます。A を B と一致させることが出来るか判定してください。

T 個のテストケースが与えられるので、それぞれに対して答えを求めてください。

部分文字列とは S の 部分文字列 とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

  • 1 \leq T \leq 3 \times 10^5
  • A, B は (, x, ) からなる長さ 1 以上 2\times 10^6 以下の文字列
  • 全てのテストケースに対する |A| + |B| の総和は 2 \times 10^6 以下 (ここで |A| は A の長さを意味する)

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケースは以下の形式で与えられる。

A
B

出力

T 行出力せよ。i 行目には i 番目のテストケースの答えを出力せよ。
各テストケースでは、A を B と一致させることが出来る場合は Yes を、そうでない場合は No を出力せよ。

入力例 1

6
(xx)x
x(xx)
(x)x
(xx)
)x()x(
)x()x(
x
(x)
(((((xx)))))x
x((((((((((xx))))))))))
((xx)xx)xx
(x((xx))x)(xx)

出力例 1

Yes
No
Yes
No
Yes
Yes

例えば 1 番目のテストケースでは、次の手順によって A を B と一致させることが出来ます。

  • A の 1 文字目から 4 文字目の (xx) を xx に置換する。操作後の A は xxx となる。
  • A の 2 文字目から 3 文字目の xx を (xx) に置換する。操作後の A は x(xx) となる。

Score : 425 points

Problem Statement

You are given a string A consisting of (, x, ).
You can perform the following two types of operations on A any number of times in any order.

  • Choose one occurrence of the substring (xx) in A and replace it with xx.
  • Choose one occurrence of the substring xx in A and replace it with (xx).

You are given a string B consisting of (, x, ). Determine whether you can make A equal to B.

You are given T test cases; solve each of them.

What is a substring A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

  • 1 \leq T \leq 3 \times 10^5
  • A and B are strings of length between 1 and 2\times 10^6, inclusive, consisting of (, x, ).
  • The sum of |A| + |B| over all test cases is at most 2 \times 10^6 (where |A| denotes the length of A).

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

A
B

Output

Output T lines. The i-th line should contain the answer to the i-th test case.
For each test case, output Yes if you can make A equal to B, and No otherwise.

Sample Input 1

6
(xx)x
x(xx)
(x)x
(xx)
)x()x(
)x()x(
x
(x)
(((((xx)))))x
x((((((((((xx))))))))))
((xx)xx)xx
(x((xx))x)(xx)

Sample Output 1

Yes
No
Yes
No
Yes
Yes

For example, in the first test case, you can make A equal to B by the following procedure:

  • Replace the (xx) from the 1st through 4th characters of A with xx. After this operation, A is xxx.
  • Replace the xx from the 2nd through 3rd characters of A with (xx). After this operation, A is x(xx).