强密码

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

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

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

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

Monocarp 还想到了两个长度为 $m$ 的字符串：$l$ 和 $r$，它们都只包含数字 $0$ 到 $9$。他希望密码的第 $i$ 位数字在 $l_i$ 和 $r_i$ 之间（包含两端）。

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

输入格式

第一行包含一个整数 $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$，都有 $l_i \le r_i$。

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

输出格式

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

样例输入 1

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

样例输出 1

YES
NO
YES
NO
YES

数据范围

对于所有数据，$1\le t\le10^4$，$1\le|s|\le3\times10^5$，$1\le m\le10$，$|l|=|r|=m$ 且 $l_i\le r_i$；所有测试用例中 $|s|$ 的总和不超过 $3\times10^5$。