## Mark and His Unfinished Essay solution codeforces

**Solution – CLICK HERE**

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 +1…slsl+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.

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

The first line of each test case contains three integers n, c, and q (1≤≤2⋅1051≤n≤2⋅105, 1≤≤401≤c≤40, and 1≤≤1041≤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 (1≤≤≤10181≤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 (1≤≤10181≤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 2⋅1052⋅105 and 104104, respectively.

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

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

m a r e a r

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.

**Solution – CLICK HERE**