该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1s
空间限制：256MB

Description

小季想给他的手机设置一个开机密码，但是他不希望别人能打开它，因此他的密码应该尽可能的复杂，对此他想出了以下标准：

• 密码的长度应该正好是 \(m\) ；
• 密码应该只由 0 到 9 的数字组成；
• 密码不能是常用密码（以字符串 \(s\) 给出）中的任意子序列（不一定连续）。

小季还想出了两个长度为 \(m\) 的字符串：\(l\) 和 \(r\) ，都只由 0 到 9 的数字组成。他希望密码中的第 \(i\) 位数字在 \(l_i\) 和 \(r_i\) 之间。

那么是否存在一个符合小季提出的所有标准的密码？

Input Format

第一行包含一个整数 \(t\)（\(1≤t≤10^4\)）- 测试用例的数量。

对于每个测试用例：

• 第一行包含一个字符串 \(s\)（ \(1≤|s|≤3⋅10^5\) ），仅由 0 到 9 的数字组成，代表常用密码。
• 第二行包含一个单一的整数 \(m\)（ \(1≤m≤10\) ）- 密码长度。
• 第三行、第四行各包含一个字符串 \(l,r\)（ \(|l|=m,|r|=m\) ），仅由 0 到 9 中的数字组成 - 每个数字的下、上限值。

保证所有的 \(l_i \le r_i\) 成立，所有测试案例中 s 的长度之和不超过 \(3⋅10^5\) 。

Output Format

对于每个测试案例，如果存在一个符合所有标准的密码，打印 "YES"。否则打印 "NO"。

Data Range

\(1≤t≤10^4,1≤|s|≤3⋅10^5,1≤m≤10,|l|=m,|r|=m,l_i \le r_i,\sum_{i=1}^{t}len(s_i) \le 3 \times 10^5\) 。

Input Example #1：

5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11

Output Example #1：

YES
NO
YES
NO
YES

Note

在第一个测试案例中，小季可以选择密码 "50"。它没有作为子序列出现在\(s\)中。

在第二个测试案例中，所有三个数字的组合，每个数字都是从 \(1\) 到 \(4\) ，符合 \(l\) 和 \(r\) 的标准。然而，它们都作为子序列出现在 \(s\) 中。例如，"314" 出现在 \([3, 5, 12]\) 位，"222" 出现在 \([2, 6, 10]\) 位。

在第三个测试案例中，小季可以选择密码 "4321" 。实际上，这是唯一符合 \(l\) 和 \(r\) 上标准的密码，并且没有作为子序列出现在 \(s\) 中。

在第四个测试案例中，只有 "49" 和 "59" 符合 \(l\) 和 \(r\) 的标准。它们都作为子序列出现在 \(s\) 中。

在第五个测试案例中，小季可以选择密码 "11" 。