[Solution] Mark and His Unfinished Essay Codeforces Solution

C. Mark and His Unfinished Essay

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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$s$ of initial length n$n$. Mark will perform the copy-pasting operation c$c$ times. Each operation is described by two integers l$l$ and r$r$, which means that Mark will append letters slsl+1…sr$s_l{s}_{l+1}\dots s_r$ to the end of string s$s$. Note that the length of s$s$ increases after this operation.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

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

Input

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

The first line of each test case contains three integers n$n$, c$c$, and q$q$ (1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$, 1≤c≤40$1\le c\le 40$, and 1≤q≤104$1\le q\le {10}^4$) — the length of the

Mark and the Online Exam Codeforces Solution

Mark and Professor Koro Codeforces Solution

Mark and Lightbulbs Codeforces Solution

Mark and His Unfinished Essay Codeforces Solution

Mark the Dust Sweeper Codeforces Solution

Mark the Photographer Codeforces Solution

 initial string s$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$s$ of length n$n$. It is guaranteed that s$s$ only contains lowercase English letters.

The following c$c$ lines describe the copy-pasting operation. Each line contains two integers l$l$ and r$r$ (1≤l≤r≤1018$1\le l\le r\le {10}^{18}$). It is also guaranteed that r$r$ does not exceed the current length of s$s$.

The last q$q$ lines of each test case describe the queries. Each line contains a single integer k$k$ (1≤k≤1018$1\le k\le {10}^{18}$). It is also guaranteed that k$k$ does not exceed the final length of s$s$.

It is guaranteed that the sum of n$n$ and q$q$ across all test cases does not exceed 2⋅105$2\cdot {10}^5$ and 104${10}^4$, respectively.

Output

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