← 返回题目列表

Codeforces · 1845/C

C. 强密码

中文机器翻译题面 查看原题

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”。