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$$$ 的数字 - 每个数字的上限。 $$$l_i \le r_i$$$ 适用于从 $$$1$$$ 到 $$$m$$$ 的所有 $$$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
注意
在第一个测试用例中,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”。