You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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?

## Input Format
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$$$.

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

## Examples
```input
5
88005553535123456
2
50
56
123412341234
3
111
444
1234
4
4321
4321
459
2
49
59
00010
2
10
11
```
```output
YES
NO
YES
NO
YES
```

## Note
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".

Now solve the problem and return the code.