# Mark and His Unfinished Essay solution codeforces

## Mark and His Unfinished Essay solution codeforces

One night, Mark realized that there is an essay due tomorrow. He hasn’t written anything yet, so Mark decided to randomly copy-paste substrings from the prompt to make the essay.

More formally, the prompt is a string s of initial length n. Mark will perform the copy-pasting operation c times. Each operation is described by two integers l and r, which means that Mark will append letters +1slsl+1…sr to the end of string s. Note that the length of s increases after this operation.

Of course, Mark needs to be able to see what has been written. After copying, Mark will ask q queries: given an integer k, determine the k-th letter of the final string s.

Input

The first line contains a single integer t (110001≤t≤1000) — the number of test cases.

The first line of each test case contains three integers nc, and q (121051≤n≤2⋅1051401≤c≤40, and 11041≤q≤104) — the length of the initial string s, the number of copy-pasting operations, and the number of queries, respectively.

The second line of each test case contains a single string s of length n. It is guaranteed that s only contains lowercase English letters.

The following c lines describe the copy-pasting operation. Each line contains two integers l and r (110181≤l≤r≤1018). It is also guaranteed that r does not exceed the current length of s.

The last q lines of each test case describe the queries. Each line contains a single integer k (110181≤k≤1018). It is also guaranteed that k does not exceed the final length of s.

It is guaranteed that the sum of n and q across all test cases does not exceed 21052⋅105 and 104104, respectively.

Output

For each query, print the k-th letter of the final string s.

Example
input

Copy
2
4 3 3
mark
1 4
5 7
3 8
1
10
12
7 3 3
creamii
2 3
3 4
2 9
9
11
12

output

Copy
m
a
r
e
a
r

Note

In the first test case, the copy-paste process is as follows.

• The first step is pasting string mark at the end, yielding the string markmark.
• The second step is pasting string mar at the end, yielding the string markmarkmar.
• The third step is pasting string rkmark at the end, yielding the string markmarkmarrkmark.

In the second test case, the copy-paste process is as follows.

• The first step is pasting string re at the end, yielding the string creamiire.
• The second step is pasting string ea at the end, yielding the string creamiireea.
• The third step is pasting string reamiire at the end, yielding the string creamiireeareamiire.