题目描述

给定由小写英文字母组成的字符串 $S,T$，以及由 0、1 组成的字符串 $X$，定义函数 $f(S,T,X)$ 如下：

• 从空字符串开始，依次对于 $i=1,2,\dots,|X|$，如果 $X$ 的第 $i$ 个字符为 0，则将 $S$ 拼接到末尾；如果为 1，则将 $T$ 拼接到末尾。最终得到的字符串即为 $f(S,T,X)$。

现在给定小写英文字母字符串 $S$，以及由 0、1 组成的字符串 $X,Y$。

请判断是否存在一个小写英文字母字符串 $T$（可以为空），使得 $f(S,T,X)=f(S,T,Y)$ 成立。

有 $t$ 组测试数据，请分别作答。

输入格式

输入按以下格式从标准输入读入。

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

每组数据格式如下：

$S\ X\ Y$

输出格式

输出 $t$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案。如果存在满足条件的 $T$，输出 Yes，否则输出 No。

样例 1

输入

3
araara
01
111
araaaa
100100
0010111
abacabac
0
1111

输出

Yes
No
No

样例 2

输入

2
empty
10101
00
empty
11111
111

输出

Yes
Yes

说明/提示

限制条件

• $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$ 为小写英文字母字符串
• $X,Y$ 为仅由 0、1 组成的字符串
• 所有测试用例中 $|S|$ 的总和不超过 $5 \times 10^5$
• 所有测试用例中 $|X|$ 的总和不超过 $5 \times 10^5$
• 所有测试用例中 $|Y|$ 的总和不超过 $5 \times 10^5$

样例解释 1

以下用 $+$ 表示字符串拼接。对于第 1 个测试用例，取 $T=$ara，则 $f(S,T,X)=S+T=$araaraara，$f(S,T,Y)=T+T+T=$araaraara，因此 $f(S,T,X)=f(S,T,Y)$ 成立。对于第 2、3 个测试用例，不存在满足条件的 $T$。

样例解释 2

$T$ 可以为空字符串。

由 ChatGPT 4.1 翻译