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

In the first testcase, Monocarp can choose password "50". It doesn't appear in $ s $ as a subsequence. In the second testcase, all combinations of three digits, each of them being from $ 1 $ to $ 4 $ , fit the criteria on $ l $ and $ r $ . However, all of them appear in $ s $ as subsequences. For example, "314" appears at positions $ [3, 5, 12] $ and "222" appears at positions $ [2, 6, 10] $ . In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on $ l $ and $ r $ . Luckily, it doesn't appear in $ s $ as a subsequence. In the fourth testcase, only "49" and "59" fit the criteria on $ l $ and $ r $ . Both of them appear in $ s $ as subsequences. In the fifth testcase, Monocarp can choose password "11".