Problem Description

For strings $ S $ and $ T $ consisting of lowercase English letters and string $ X $ consisting of 0 and 1, we define a string $ f(S,T,X) $ as follows:

• Starting from an empty string, for each $i=1,2,\dots,|X|$, append $ S $ to the end if the $ i $-th character of $ X $ is 0, or append $ T $ if it is 1.

You are given a string $ S $ consisting of lowercase English letters and strings $ X $ and $ Y $ consisting of 0 and 1.

Determine if there exists a string $ T $ (which can be an empty string) such that $ f(S,T,X)=f(S,T,Y) $.

You will be given $ t $ test cases, and you need to solve each one.

Input Format

The input is given from the standard input in the following format:

$ t $ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_t$

Each case is given in the following format:

$ S $ $ X $ $ Y $

Output Format

Output $ t $ lines. The $ i $-th line should contain Yes if there exists a $ T $ that satisfies the condition for the $ i $-th test case, and No otherwise.

Sample Input and Output

Sample Input #1

3
araara
01
111
araaaa
100100
0010111
abacabac
0
1111

Sample Output #1

Yes
No
No

Sample Input #2

2
empty
10101
00
empty
11111
111

Sample Output #2

Yes
Yes

Notes/Hints

Constraints

• $1 \leq t \leq 5 \times 10^5$
• $1 \leq |S| \leq 5 \times 10^5$
• $1 \leq |X|, |Y| \leq 5 \times 10^5$
• $ S $ is a string consisting of lowercase English letters.
• $ X $ and $ Y $ are strings consisting of 0 and 1.
• For the test cases in one input, the sum of $ |S| $ is at most $5 \times 10^5$.
• For the test cases in one input, the sum of $ |X| $ is at most $5 \times 10^5$.
• For the test cases in one input, the sum of $ |Y| $ is at most $5 \times 10^5$.

Sample Explanation 1

Using concatenation denoted by $ + $, for the first test case, if $ T = $ara, then $ f(S,T,X) = S + T = $araaraara and $ f(S,T,Y) = T + T + T = $araaraara, so $ f(S,T,X) = f(S,T,Y) $. For the second and third test cases, no $ T $ satisfies the condition.

Sample Explanation 2

$ T $ can be an empty string.

见题面 Input 部分

见题面 Output 部分