恼人的字符串问题

时间限制：2s
空间限制：512MB

题目描述

给定小写英文字母字符串 $S,T$ 和二进制字符串 $X$，定义 $f(S,T,X)$：初始为空串，从左到右扫描 $X$；遇到 0 就在末尾拼接 $S$，遇到 1 就在末尾拼接 $T$。

现在给定小写英文字母字符串 $S$ 以及二进制字符串 $X,Y$。请判断是否存在一个小写英文字母字符串 $T$（允许为空串），使得 $f(S,T,X)=f(S,T,Y)$。

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

输入格式

第一行一个整数 $t$。接下来 $t$ 行，每行依次给出三个字符串 $S,X,Y$。

输出格式

输出 $t$ 行。如果第 $i$ 组数据存在满足条件的 $T$，第 $i$ 行输出 Yes；否则输出 No。

样例输入 1

3
araara 01 111
araaaa 100100 0010111
abacabac 0 1111

样例输出 1

Yes
No
No

样例输入 2

2
empty 10101 00
empty 11111 111

样例输出 2

Yes
Yes

数据范围

• $1\le t\le 5\times10^5$；
• $1\le \vert S\vert ,\vert X\vert ,\vert Y\vert \le 5\times10^5$；
• $S$ 仅由小写英文字母组成，$X,Y$ 仅由 0、1 组成；
• 所有测试数据中 $\vert S\vert$ 的总和、$\vert X\vert$ 的总和、$\vert Y\vert$ 的总和分别不超过 $5\times10^5$。