CF1845C.Strong Password

Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password.

He wants his password to be as strong as possible, so he came up with the following criteria:

• the length of the password should be exactly $m$;
• the password should only consist of digits from $0$ to $9$;
• the password should not appear in the password database (given as a string $s$) as a subsequence (not necessarily contiguous).

Monocarp also came up with two strings of length $m$: $l$ and $r$, both consisting only of digits from $0$ to $9$. He wants the $i$-th digit of his password to be between $l_i$ and $r_i$, inclusive.

Does there exist a password that fits all criteria?

Monocarp 终于鼓起勇气在 ForceCoders 上注册了。他想好了用户名，但仍在思考密码。

他希望自己的密码尽可能强，因此制定了以下要求：

• 密码长度必须恰好为 $m$；
• 密码只能由数字 $0$ 到 $9$ 组成；
• 密码不能作为子序列（不一定是连续的）出现在密码数据库中（以字符串 $s$ 给出）。

此外，Monocarp 还构造了两个长度均为 $m$ 的字符串 $l$ 和 $r$，二者均由数字 $0$ 到 $9$ 组成。他要求自己密码的第 $i$ 位数字必须在 $l_i$ 和 $r_i$ 之间（含端点）。

是否存在一个满足所有条件的密码？

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting only of digits from $0$ to $9$ — the password database.

The second line contains a single integer $m$ ($1 \le m \le 10$) — the required length of the password.

The third line contains a string $l$ ($|l| = m$), consisting only of digits from $0$ to $9$ — the lower restriction on each digit.

The fourth line contains a string $r$ ($|r| = m$), consisting only of digits from $0$ to $9$ — the upper restriction on each digit. $l_i \le r_i$ for all $i$ from $1$ to $m$.

The sum of lengths of $s$ over all testcases doesn't exceed $3 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个字符串 $s$（$1 \le |s| \le 3 \cdot 10^5$），仅由数字 $0$ 到 $9$ 组成 —— 密码数据库。

每个测试用例的第二行包含一个整数 $m$（$1 \le m \le 10$）—— 所需密码的长度。

每个测试用例的第三行包含一个字符串 $l$（$|l| = m$），仅由数字 $0$ 到 $9$ 组成 —— 每一位数字的下界限制。

每个测试用例的第四行包含一个字符串 $r$（$|r| = m$），仅由数字 $0$ 到 $9$ 组成 —— 每一位数字的上界限制。对所有 $i$（$1 \le i \le m$），满足 $l_i \le r_i$。

所有测试用例中字符串 $s$ 的长度总和不超过 $3 \cdot 10^5$。

For each testcase, print "YES" if there exists a password that fits all criteria. Print "NO" otherwise.

对于每个测试用例，如果存在一个满足所有条件的密码，则输出 “YES”；否则输出 “NO”。

In the first testcase, Monocarp can choose password "50". It doesn't appear in $s$ as a subsequence.

In the second testcase, all combinations of three digits, each of them being from $1$ to $4$, fit the criteria on $l$ and $r$. However, all of them appear in $s$ as subsequences. For example, "314" appears at positions $[3, 5, 12]$ and "222" appears at positions $[2, 6, 10]$.

In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on $l$ and $r$. Luckily, it doesn't appear in $s$ as a subsequence.

In the fourth testcase, only "49" and "59" fit the criteria on $l$ and $r$. Both of them appear in $s$ as subsequences.

In the fifth testcase, Monocarp can choose password "11".

在第一个测试用例中，Monocarp 可以选择密码 “50”。它不会作为子序列出现在 $s$ 中。

在第二个测试用例中，所有由三个数字组成的组合（每个数字均取自 $1$ 到 $4$）均满足关于 $l$ 和 $r$ 的限制条件。然而，它们全部都会作为子序列出现在 $s$ 中。例如，“314” 出现在位置 $[3, 5, 12]$ 上，而 “222” 出现在位置 $[2, 6, 10]$ 上。

在第三个测试用例中，Monocarp 可以选择密码 “4321”。实际上，这是唯一一个满足关于 $l$ 和 $r$ 的限制条件的密码。幸运的是，它不会作为子序列出现在 $s$ 中。

在第四个测试用例中，仅有 “49” 和 “59” 满足关于 $l$ 和 $r$ 的限制条件。但它们均会作为子序列出现在 $s$ 中。

在第五个测试用例中，Monocarp 可以选择密码 “11”。