A15996 · 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?

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$ .

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

输入 #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