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 $s_l s_{l+1} \ldots s_r$ 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$ ($1\leq t\leq 1000$) — the number of test cases.

The first line of each test case contains three integers $n$, $c$, and $q$ ($1\leq n\leq 2\cdot 10^5$, $1\leq c\leq 40$, and $1\leq q\leq 10^4$) — 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\leq l\leq r\leq 10^{18}$). 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\leq k\leq 10^{18}$). 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\cdot 10^5$ and $10^4$, respectively.


-----Output-----

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


-----Examples-----

Input
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
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 ${mark}{{mark}}$.

The second step is pasting string ${mar}$ at the end, yielding the string ${markmark}{{mar}}$.

The third step is pasting string ${rkmark}$ at the end, yielding the string ${markmarkmar}{{rkmark}}$.

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 ${creamii}{{re}}$.

The second step is pasting string ${ea}$ at the end, yielding the string ${creamiire}{{ea}}$.

The third step is pasting string ${reamiire}$ at the end, yielding the string ${creamiireea}{{reamiire}}$.

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation

Complete search


Solutions:
import sys

def solve(string, reps, idx, pos):
	if idx < 0:
		return string[pos - 1]
	(l, ls) = reps[idx]
	if pos < ls:
		return solve(string, reps, idx - 1, pos)
	else:
		return solve(string, reps, idx - 1, l + (pos - ls))
for i in range(int(next(sys.stdin).strip())):
	(n, c, q) = [int(x) for x in next(sys.stdin).strip().split()]
	string = next(sys.stdin).strip()
	repeats = []
	query = []
	for idx in range(c):
		(l, r) = [int(x) for x in next(sys.stdin).strip().split(' ')]
		repeats.append((l, n + 1))
		n = n + r - l + 1
	for idx in range(q):
		query = int(next(sys.stdin).strip())
		print(solve(string, repeats, c - 1, query))


from bisect import bisect_left
import sys
sys.setrecursionlimit(100000)
for item in range(int(input())):
	(n, c, q) = list((int(i) for i in sys.stdin.readline().split()))
	s = sys.stdin.readline().strip()
	intervals = []
	intervals = []
	intervals.append([1, n])
	lens = []
	lens.append(n)
	for j in range(c):
		(a, b) = list((int(i) for i in sys.stdin.readline().split()))
		intervals.append((a, b))
		lens.append(b - a + 1 + lens[-1])
	for j in range(q):
		x = int(sys.stdin.readline())
		ind = bisect_left(lens, x)
		while x > n:
			ind = bisect_left(lens, x)
			x = x - lens[ind - 1] - 1 + intervals[ind][0]
		print(s[x - 1])


ans = ''
for t in range(int(input())):
	(n, c, q) = list(map(int, input().split()))
	string = input()
	left = [0] * (c + 1)
	right = [0] * (c + 1)
	diff = [0] * (c + 1)
	left[0] = 0
	right[0] = n
	for i in range(1, c + 1):
		(l, r) = list(map(int, input().split()))
		l -= 1
		r -= 1
		left[i] = right[i - 1]
		right[i] = left[i] + (r - l + 1)
		diff[i] = left[i] - l
	for _ in range(q):
		k = int(input())
		k -= 1
		for i in range(c, 0, -1):
			if k < left[i]:
				continue
			else:
				k -= diff[i]
		ans += string[k] + '\n'
print(ans)


def solve(n, s, array, queries):
	lengths = [n]
	for (l, r) in array:
		lengths.append(lengths[-1] + (r - l + 1))
	res = ''
	for q in queries:
		temp = q
		for i in range(len(lengths), 0, -1):
			if temp > lengths[i - 1]:
				temp -= lengths[i - 1]
				temp += array[i - 1][0] - 1
		res += s[temp - 1]
	return res
T = int(input())
for _ in range(T):
	(n, c, q) = map(int, input().split())
	s = input()
	array = [list(map(int, input().split())) for _ in range(c)]
	queries = [int(input()) for _ in range(q)]
	res = solve(n, s, array, queries)
	for let in res:
		print(let)


import bisect

def main():
	for t in range(int(input())):
		(n, c, q) = map(int, input().split())
		s = '0' + input()
		d = [n]
		dd = [0]
		for i in range(c):
			(l, r) = map(int, input().split())
			d.append(d[-1] + r - l + 1)
			dd.append([l, r])
		for i in range(q):
			x = int(input())
			while x > n:
				j = bisect.bisect_left(d, x)
				x = dd[j][0] + x - d[j - 1] - 1
			print(s[x])
main()


import sys
from math import *
from bisect import *
from heapq import *
from collections import *
from functools import *
sys.setrecursionlimit(100000)
x = int(input())

def op(x):
	if x <= len(s):
		return x
	idx = bisect_left(index, x)
	(l, r) = temp[idx]
	n = index[idx]
	return op(x + r - n)
for _ in range(x):
	(n, c, q) = map(int, input().split())
	s = input()
	temp = [[1, n]]
	index = [n]
	for i in range(c):
		(l, r) = map(int, input().split())
		index.append(index[-1] + r - l + 1)
		temp.append([l, r])
	for i in range(q):
		print(s[op(int(input())) - 1])


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	(n, c, q) = map(int, input().split())
	s = input()
	net = []
	query = []
	curr = n
	for i in range(c):
		(l, r) = map(int, input().split())
		query.append((l, r))
		length = r - l + 1
		ok1 = curr + 1
		ok2 = curr + length
		net.append((ok1, ok2))
		curr = curr + length
	for j in range(q):
		k = int(input())
		(start, end) = (0, 1)
		for i in range(c - 1, -1, -1):
			if k >= net[i][start] and k <= net[i][end]:
				gap = k - net[i][start]
				k = query[i][start] + gap
		print(s[k - 1])
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
import bisect
sys.setrecursionlimit(10 ** 6)

def dfs(x, s, n, A, B):
	if 0 <= x < n:
		return s[x]
	else:
		index = bisect.bisect_right(A, x) - 1
		return dfs(x - B[index], s, n, A, B)

def main():
	t = int(input())
	for _ in range(t):
		(n, c, q) = map(int, input().split())
		s = input()
		A = []
		B = []
		length = len(s)
		for _ in range(c):
			(l, r) = map(int, input().split())
			l -= 1
			r -= 1
			A.append(length)
			B.append(length - l)
			length += r - l + 1
		for _ in range(q):
			x = int(input())
			x -= 1
			ans = dfs(x, s, n, A, B)
			print(ans)
main()


import math, bisect
xx = int(input())

def cal(qq):
	if qq < n:
		return s[qq]
	while qq >= n:
		t = bisect.bisect(arr, qq)
		qq = qq - arr[t - 1] + p[t - 1][0]
	return s[qq]
for jj in range(xx):
	(n, c, q) = [int(i) for i in input().split(' ')]
	s = input()
	fe = n
	arr = [0]
	p = [0]
	for i in range(c):
		(a, b) = [int(i) - 1 for i in input().split(' ')]
		arr.append(fe)
		fe += b - a + 1
		p.append([a, b])
	for i in range(q):
		qq = int(input()) - 1
		print(cal(qq))


from bisect import bisect_right

def miis():
	return map(int, input().split())
for _ in range(int(input())):
	(n, c, q) = miis()
	s = input()
	z = [1, n + 1]
	cc = []
	for i in range(c):
		(l, r) = miis()
		cc.append((l, r))
		z.append(z[-1] + (r - l + 1))
	for i in range(q):
		k = int(input())
		while k > n:
			m = bisect_right(z, k) - 1
			k = cc[m - 1][0] + k - z[m]
		print(s[k - 1])


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, c, q) = R()
	s = input()
	a = []
	while c:
		c -= 1
		(l, r) = R()
		a = [(n, n - l + 1)] + a
		n += r - l + 1
	while q:
		q -= 1
		(k,) = R()
		for (x, y) in a:
			k -= y * (k > x)
		print(s[k - 1])


for _ in range(int(input())):
	(n, c, q) = input().split()
	(n, c, q) = (int(n), int(c), int(q))
	s = input()
	arr = []
	for i in range(c):
		(l, r) = input().split(' ')
		(l, r) = (int(l), int(r))
		arr.insert(0, (n, l))
		n += r - l + 1
	for i in range(q):
		k = int(input())
		for p in arr:
			if p[0] < k:
				k -= p[0] - p[1] + 1
		print(s[k - 1])


from bisect import bisect_left
T = int(input())
for _ in range(T):
	(n, c, q) = map(int, input().split())
	s = ' ' + input()
	length = [len(s) - 1]
	add_ons = []
	cur_length = len(s) - 1
	start_length = len(s) - 1
	for o in range(c):
		(start, end) = map(int, input().split())
		cur_length += end - start + 1
		length.append(cur_length)
		add_ons.append([start, end])
	for o in range(q):
		index = int(input())
		while index > start_length:
			mark = bisect_left(length, index) - 1
			index = add_ons[mark][0] + (index - length[mark]) - 1
		print(s[index])


t = int(input())
for i in range(t):
	(n, c, q) = map(int, input().split())
	s = input()
	left = [0]
	right = [n]
	diff = [0]
	for i in range(1, c + 1):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		left.append(right[i - 1])
		right.append(left[i] + (r - l + 1))
		diff.append(left[i] - l)
	for i in range(q):
		k = int(input())
		k -= 1
		for i in range(c, 0, -1):
			if k < left[i]:
				continue
			else:
				k -= diff[i]
		print(s[k])


t = int(input())
from bisect import bisect_left
while t:
	t -= 1
	(a, b, c) = map(int, input().split())
	s = input()
	intervals = [[1, a]]
	ele = [a]
	for j in range(b):
		(x, y) = map(int, input().split())
		intervals.append([x, y])
		ele.append(y - x + 1)
	pre = [ele[0]]
	for j in range(1, len(ele)):
		pre.append(pre[-1] + ele[j])
	for j in range(0, c):
		g = int(input())
		while g > len(s):
			vayu = bisect_left(pre, g)
			g = intervals[vayu][0] + g - pre[vayu - 1] - 1
		print(s[g - 1])


from bisect import *
R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, c, q) = R()
	s = input()
	d = {}
	while c:
		c -= 1
		(l, r) = R()
		d[n] = n - l + 1
		n += r - l + 1
	(*a,) = d
	while q:
		q -= 1
		(k,) = R()
		k -= 1
		while (i := bisect(a, k)):
			k -= d[a[i - 1]]
		print(s[k])


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	li = []
	for i in range(c):
		(l, r) = map(int, input().split())
		li.append([n, l])
		n = n + r - l + 1
	for i in range(q):
		k = int(input())
		for j in range(len(li) - 1, -1, -1):
			if k > li[j][0]:
				k -= li[j][0] - li[j][1] + 1
		print(s[k - 1])


import bisect
for _ in range(int(input())):
	(n, c, q) = list(map(int, input().split()))
	s = input()
	li = [[1, n]]
	lnt = [n]
	for i in range(c):
		(a, b) = list(map(int, input().split()))
		li.append([a, b])
		lnt.append(lnt[-1] + (b - a + 1))
	for i in range(q):
		k = int(input())
		tt = bisect.bisect(lnt, k)
		if lnt[tt - 1] == k:
			tt = tt - 1
		temp = lnt[tt] - k
		k = li[tt][1] - temp
		while k > n:
			tt = bisect.bisect(lnt, k)
			if lnt[tt - 1] == k:
				tt = tt - 1
			temp = lnt[tt] - k
			k = li[tt][1] - temp
		print(s[k - 1])


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = str(input())
	length = []
	length.append(n)
	ln = n
	ops = []
	ops.append((1, n))
	for i in range(c):
		(l, r) = map(int, input().split())
		ln += r - l + 1
		length.append(ln)
		ops.append((l, r))
	for j in range(q):
		k = int(input())
		for i in range(c - 1, -1, -1):
			if k > length[i]:
				k = ops[i + 1][0] + k - length[i] - 1
		print(s[k - 1])


import bisect

def query(s, c, copy, q):
	if q <= len(s):
		return s[q - 1]
	a = bisect.bisect_left(c, q)
	b = q - c[a - 1] + copy[a - 1][0] - 1
	return query(s, c, copy, b)
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	c1 = [len(s)]
	copy = []
	for i in range(c):
		(a, b) = map(int, input().split())
		copy.append((a, b))
		c1.append(c1[-1] + b - a + 1)
	for i in range(q):
		print(query(s, c1, copy, int(input())))


import bisect
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = str(input())
	ranges = [(-1, -1)]
	pref = [n]
	for _ in range(c):
		(l, r) = map(int, input().split())
		ranges.append((l, r))
		pref.append(pref[-1] + r - l + 1)
	for _ in range(q):
		k = int(input())
		while k > len(s):
			ind = bisect.bisect_left(pref, k)
			rem = k - pref[ind - 1]
			k = ranges[ind][0] + rem - 1
			ind -= 1
		print(s[max(0, k - 1)])


t = int(input())
while t:
	(p, q, r) = map(int, input().split())
	s = input()
	l = []
	check = []
	curr = p
	for i in range(q):
		(j, k) = map(int, input().split())
		l.append([j, k])
		g = l[i][1] - l[i][0] + 1
		check.append([p + 1, p + g])
		p = check[i][1]
	for i in range(r):
		idx = int(input())
		for j in range(q - 1, -1, -1):
			if idx >= check[j][0] and idx <= check[j][1]:
				gap = idx - check[j][0]
				idx = l[j][0] + gap
		print(s[idx - 1])
	t -= 1


out = []
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	ins = [[n, 0, 0]]
	for i in range(c):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		ins.append([ins[-1][0] + r - l + 1, l, r])
	for i in range(q):
		x = int(input()) - 1
		cur = c
		while cur > 0:
			while cur > 0 and ins[cur - 1][0] > x:
				cur -= 1
			if cur == 0:
				break
			x = x - ins[cur - 1][0] + ins[cur][1]
		out.append(s[x])
for i in out:
	print(i)


from bisect import bisect_left
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	mp = {1: (1, n)}
	st = n + 1
	nums = [1]
	for i in range(c):
		(l, r) = map(int, input().split())
		mp[st] = (l, r)
		nums.append(st)
		st += r - l + 1
	for i in range(q):
		x = int(input())
		while x > n:
			pos = bisect_left(nums, x) - 1
			if pos < c and nums[pos + 1] == x:
				pos += 1
			(l, r) = mp[nums[pos]]
			x = x - nums[pos] + l
		print(s[x - 1])


t = int(input())
while t:
	t -= 1
	(n, c, q) = [int(x) for x in input().split()]
	s = input()
	a = []
	ini = n
	ls = [ini]
	for i in range(c):
		(l, r) = [int(x) for x in input().split()]
		a.append((l, r))
		ini += r - l + 1
		ls.append(ini)
	for i in range(q):
		k = int(input())
		for (i, x) in enumerate(ls):
			if x >= k:
				for j in range(i - 1, -1, -1):
					if k > ls[j]:
						d = k - ls[j]
						k = d + a[j][0] - 1
				print(s[k - 1])
				break


t = int(input())
for _ in range(t):
	(n, c, q) = [int(k) for k in input().split()]
	s = input()
	l_arr = []
	r_arr = []
	query = []
	curr_end = n
	for i in range(1, c + 1):
		(l, r) = [int(k) for k in input().split()]
		query.append((l, r))
		q_len = r - l + 1
		l_arr.append(curr_end + 1)
		r_arr.append(curr_end + q_len)
		curr_end = r_arr[-1]
	for i in range(q):
		idx = int(input())
		for j in range(c - 1, -1, -1):
			left = l_arr[j]
			right = r_arr[j]
			if left <= idx <= right:
				gap = idx - left
				idx = query[j][0] + gap
		print(s[idx - 1])


from collections import deque
import bisect
t = int(input())
for _ in range(t):
	(n, c, q) = [int(x) for x in input().split()]
	s = input()
	intervals = []
	deduct = []
	m = n
	for _ in range(c):
		(l, r) = [int(x) - 1 for x in input().split()]
		intervals.append([m, m + r - l])
		deduct.append(m - l)
		m += r - l + 1
	for _ in range(q):
		k = int(input()) - 1
		i = c - 1
		while k >= n:
			(a, b) = intervals[i]
			if a <= k <= b:
				k -= deduct[i]
			i -= 1
		print(s[k])


t = int(input())
for _ in range(t):
	(n, c, q) = map(int, input().split())
	s = input().strip()
	strips = []
	lengths = [n]
	for i in range(c):
		(l, r) = map(int, input().split())
		strips.append(l)
		lengths.append(lengths[-1] + r - l + 1)
	for i in range(q):
		k = int(input())
		for j in range(c):
			last_length = lengths[-j - 2]
			if k > last_length:
				k = k - last_length + strips[-j - 1] - 1
		print(s[k - 1])


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	a = n
	d = [n]
	w = []
	for _ in range(c):
		(l, r) = map(int, input().split())
		a += r - l + 1
		d.append(a)
		w.append(l)
	for _ in range(q):
		k = int(input())
		i = len(d) - 1
		while k > n:
			if d[i] >= k > d[i - 1]:
				k -= d[i - 1]
				k += w[i - 1] - 1
			i -= 1
		print(s[k - 1])


from bisect import *
for t in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = str(input())
	ind = [(0, n - 1, (0, n - 1))]
	for i in range(c):
		(l, r) = map(int, input().split())
		ind.append((ind[-1][1] + 1, ind[-1][1] + 1 + r - l, (l - 1, r - 1)))
	for Q in range(q):
		k = int(input()) - 1
		while k > n - 1:
			i = bisect_right(ind, (k + 1, 0, (0, 0))) - 1
			k = ind[i][2][0] + (k - ind[i][0])
		print(s[k])


t = int(input())
for _ in range(t):
	(n, c, q) = map(int, input().split())
	s = input()
	notes = []
	currentlength = [n]
	for _ in range(c):
		lst = list(map(int, input().split()))
		if currentlength[-1] <= 10 ** 18:
			notes.append(lst)
			currentlength.append(currentlength[-1] + lst[1] - lst[0] + 1)
	for _ in range(q):
		pos = int(input())
		for i in range(c + 1):
			if currentlength[i] >= pos:
				break
		for k in range(i + 1, 0, -1):
			if pos > currentlength[k - 1]:
				pos = notes[k - 1][0] + pos - currentlength[k - 1] - 1
		print(s[pos - 1])


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	a = [(1, n)]
	ln = [n]
	for _ in range(c):
		(l, r) = map(int, input().split())
		ln.append(ln[-1] + (r - l + 1))
		a.append((l, r))
	for _ in range(q):
		k = int(input())
		idx = 0
		for i in range(c + 1):
			if ln[i] >= k:
				idx = i
				break
		while idx > 0:
			if ln[idx - 1] >= k:
				idx -= 1
			else:
				k = k - ln[idx - 1] + a[idx][0] - 1
				idx -= 1
		print(s[k - 1])


t = int(input())
while t:
	s = input().split()
	(n, c, q) = map(int, s)
	s = input()
	ops = []
	bndry = [[0, len(s)]]
	for i in range(c):
		a = input().split()
		(l, r) = map(int, a)
		l -= 1
		r -= 1
		cur = [bndry[-1][1], bndry[-1][1] + r - l + 1]
		bndry.append(cur)
		ops.append([l, r])
	qrys = []
	for i in range(q):
		k = int(input())
		k -= 1
		for j in range(len(bndry) - 1, -1, -1):
			b = bndry[j]
			if j == 0:
				print(s[k])
				break
			if b[0] <= k < b[1]:
				gap = k - b[0]
				k = ops[j - 1][0] + gap
	t -= 1


T = int(input())
for _ in range(T):
	(N, C, Q) = map(int, input().split())
	S = input().strip()
	lr = []
	le = len(S)
	for i in range(C):
		(l, r) = map(int, input().split())
		lr.append((l, r))
		le += r - l + 1
	leo = le
	lr = lr[::-1]
	for i in range(Q):
		le = leo
		k = int(input())
		for (l, r) in lr:
			s = le - (r - l)
			if s <= k and k <= le:
				k = l + (k - s)
			le -= r - l + 1
		print(S[k - 1])


from bisect import bisect_right
for _ in ' ' * int(input()):
	(n, c, q) = map(int, input().split())
	s = input()
	c_l = []
	ss = [1, n]
	for __ in ' ' * c:
		(l, r) = map(int, input().split())
		c_l.append((l, r))
		ss.append(ss[-1] + r - l + 1)
	for ___ in ' ' * q:
		k = int(input())
		while k > n:
			zhu = bisect_right(ss, k) - 1
			if k in ss:
				zhu -= 1
			c_index = zhu - 1
			l = c_l[c_index][0]
			k = l + k - ss[zhu] - 1
		print(s[k - 1])


def solve():
	(n, c, q) = list(map(int, input().split()))
	s = input()
	marz = [(1, n)]
	tah = [n]
	for _ in range(c):
		(l, r) = map(int, input().split())
		marz.append((l, r))
		tah.append(tah[-1] + r - l + 1)
	for _ in range(q):
		ind = int(input())
		position = 0
		while True:
			for i in range(len(tah)):
				if tah[i] >= ind:
					position = i
					break
			ind = marz[position][1] - (tah[position] - ind)
			if ind <= n:
				break
		print(s[ind - 1])
for _ in range(int(input())):
	solve()


def find(k):
	if k <= N:
		return k
	for i in v:
		if k - i < 0:
			continue
		return find(k - i + d[i])
for _ in range(int(input())):
	(N, C, Q) = map(int, input().split())
	s = list(input().strip())
	d = dict()
	d[1] = 1
	x = N + 1
	for c in range(C):
		(l, r) = map(int, input().split())
		d[x] = l
		x += r - l + 1
	v = list(d.keys())
	v.sort(reverse=True)
	for q in range(Q):
		k = int(input())
		print(s[find(k) - 1])


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = str(input())
	l = [[1, n]]
	t = [n]
	for _ in range(c):
		(a, b) = map(int, input().split())
		l.append([a, b])
		t.append(t[-1] + b - a + 1)

	def ceiling_of_element(a, x):
		n = len(a)
		start = 0
		end = n - 1
		res = -1
		while start <= end:
			mid = (start + end) // 2
			if a[mid] == x:
				return mid
			elif x > a[mid]:
				start = mid + 1
			else:
				res = mid
				end = mid - 1
		return res
	for _ in range(q):
		x = int(input())
		i = ceiling_of_element(t, x)
		aaa = l[i][1] - t[i] + x
		while aaa > n:
			i = ceiling_of_element(t, aaa)
			aaa = l[i][1] - t[i] + aaa
		if aaa == 0:
			aaa = n
		print(s[aaa - 1])


def binary_search(list1, n):
	low = 0
	high = len(list1) - 1
	mid = 0
	while low < high:
		mid = (high + low + 1) // 2
		if list1[mid] < n:
			low = mid
		elif list1[mid] > n:
			high = mid - 1
		else:
			return mid
	return low
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	string = input()
	n = len(string)
	initial = n
	limits = [0]
	starting = [0]
	for i in range(c):
		(l, r) = map(int, input().split())
		limits.append(l - 1)
		starting.append(n)
		n = n + r - l + 1
	for j in range(q):
		k = int(input())
		indx = binary_search(starting, k - 1)
		needed = k - starting[indx] + limits[indx] - 1
		while needed > initial - 1:
			indx = binary_search(starting, needed)
			needed = needed - starting[indx] + limits[indx]
		print(string[needed])


t = int(input())

def findindex(array1, array2, n, len_of_s):
	position = n
	while position > len_of_s:
		for i in range(len(array2) - 1, -1, -1):
			if array2[i][0] <= position:
				pos = i
				break
		position = array1[pos][0] + position - array2[pos][0]
	return position
while t > 0:
	(n, c, q) = map(int, input().split(' '))
	s = str(input())
	copyop = []
	for i in range(c):
		copyop.append(list(map(int, input().split(' ')[:2])))
	queries = []
	for i in range(q):
		queries.append(int(input()))
	original_pos = []
	currend = len(s)
	for (l, r) in copyop:
		original_pos.append([currend + 1, currend + 1 + r - l])
		currend = currend + 1 + r - l
	for i in queries:
		if i <= len(s):
			print(s[i - 1])
		else:
			pos = findindex(copyop, original_pos, i, len(s))
			print(s[pos - 1])
	t -= 1


for iii in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	q1 = []
	for i in range(c):
		q2 = list(map(int, input().split()))
		q1.append(q2)
	pre = [n]
	for i in range(c):
		x = pre[i] + q1[i][1] - q1[i][0] + 1
		pre.append(x)

	def qwe(x):
		if x <= n:
			return s[x - 1]
		dis = -1
		ind = -1
		for i in range(c + 1):
			if x <= pre[i]:
				dis = x - pre[i - 1]
				ind = i - 1
				break
		dis1 = q1[ind][0] + dis - 1
		return qwe(dis1)
	for i in range(q):
		x = int(input())
		print(qwe(x))


t = int(input())
for tt in range(t):
	(n, c, q) = map(int, input().split())
	s = input()
	l = []
	r = []
	a = []
	a.append(n)
	for i in range(c):
		(ll, rr) = map(int, input().split())
		ll -= 1
		rr -= 1
		l.append(ll)
		r.append(rr)
		a.append(a[len(a) - 1] + rr - ll + 1)
	for qq in range(q):
		k = int(input())
		k -= 1
		while k >= n:
			ll = 0
			rr = len(a)
			while rr - ll > 0:
				m = (ll + rr) // 2
				if a[m] > k:
					rr = m
				elif m < len(a) - 1 and a[m + 1] > k:
					k = l[m] + k - a[m]
					break
				else:
					ll = m
		print(s[k])


def low_bound(list, item):
	low = -1
	high = len(list)
	while high - low > 1:
		mid = (low + high) // 2
		if list[mid][0] < item:
			low = mid
		else:
			high = mid
	return low + 1
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	b = [[0, 0]] * c
	ll = n
	for i in range(c):
		(l, r) = map(int, input().split())
		ll += r - l + 1
		b[i] = [ll, r]
	for _ in range(q):
		k = int(input())
		while k > n:
			k = b[low_bound(b, k)][1] - b[low_bound(b, k)][0] + k
		print(s[k - 1])


def get_character(n):
	for i in range(c + 1):
		if n <= list[i][0]:
			if i != 0:
				z = n - list[i - 1][0]
				character = list[i][1] + z - 1
				return get_character(character)
			else:
				return string[n - 1]
for _ in range(int(input())):
	global list
	global string
	global c
	(m, c, q) = map(int, input().split())
	string = input()
	list = [[m, 1]]
	for i in range(c):
		(l, r) = map(int, input().split())
		m += r - l + 1
		list.append([m, l])
	for _ in range(q):
		print(get_character(int(input())))


for w in range(0, int(input())):
	[n, c, q] = [int(x) for x in input().split()]
	s = input()
	ranges = [[0, n - 1]]
	thresh = [n]
	cur = n
	for j in range(c):
		(l, r) = [int(x) for x in input().split()]
		ranges.append([l - 1, r - 1])
		cur += r - l + 1
		thresh.append(cur)
	for j in range(q):
		k = int(input()) - 1
		while k >= n:
			i = c
			while thresh[i] > k:
				i -= 1
			k = k - thresh[i] + ranges[i + 1][0]
		print(s[k])


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, c, q) = map(int, sys.stdin.readline().split())
	s = input()
	dic = {}
	le = n
	dic[1, n] = s
	for j in range(c):
		(l, r) = map(int, sys.stdin.readline().split())
		ele = r - l + 1
		dic[le + 1, le + ele] = [l, r]
		le += ele

	def fun(a):
		if a >= 1 and a <= n:
			return s[a - 1]
		tup = (-1, -1)
		for f in dic.keys():
			l = f[0]
			r = f[1]
			if a >= l and a <= r:
				tup = f
				break
		c = dic[tup][0]
		d = dic[tup][1]
		dif = a - tup[0]
		return fun(c + dif)
	for j in range(q):
		k = int(sys.stdin.readline())
		print(fun(k))


t = int(input())
for tc in range(t):
	(n, c, q) = map(int, input().split())
	s = input()
	start = []
	end = []
	length = [n]
	for i in range(c):
		(S, E) = map(int, input().split())
		start.append(S)
		end.append(E)
		length.append(length[-1] + E - S + 1)
	for query in range(q):
		k = int(input())
		while k > n:
			r = 0
			for i in range(len(length)):
				if k <= length[i]:
					r = i
					break
			k += start[r - 1] - length[r - 1] - 1
		print(s[k - 1])


for _ in range(int(input())):
	(n, c, q) = list(map(int, input().split(' ')))
	s = input()
	dic = {}
	il = []
	si = n + 1
	for i in range(c):
		(l, r) = list(map(int, input().split(' ')))
		t = (si, si + r - l)
		dic[t] = l
		il.append(t)
		si = si + r - l + 1
	for i in range(q):
		rn = int(input())
		while rn > n:
			for i in il:
				if i[0] <= rn <= i[1]:
					ri = dic[i] + rn - i[0]
					rn = ri
					break
		print(s[rn - 1])


def find_char(s, c_s, lens_after_c, idx):
	if idx < len(s):
		return s[idx]
	paste_idx = 0
	while idx > lens_after_c[paste_idx] - 1:
		paste_idx += 1
	paste_idx -= 1
	idx = idx - lens_after_c[paste_idx] + c_s[paste_idx][0] - 1
	return find_char(s, c_s, lens_after_c, idx)

def main():
	i = int(input())
	for _ in range(i):
		(n, c, q) = [int(x) for x in input().strip('\r\n').split()]
		c_s = []
		lens_after_c = [n]
		s = input().strip('\r\n')
		for _ in range(c):
			c_s.append([int(x) for x in input().strip('\r\n').split()])
			lens_after_c.append(lens_after_c[-1] + c_s[-1][1] - c_s[-1][0] + 1)
		for _ in range(q):
			_q = int(input().strip('\r\n')) - 1
			print(find_char(s, c_s, lens_after_c, _q))
main()


for i in range(int(input())):
	(n, c, q) = map(int, input().split())
	a = input()
	copyPastINtervals = [(1, n)]
	copyPastRanges = [n]
	for i in range(c):
		(l, r) = map(int, input().split())
		copyPastINtervals.append((l, r))
		copyPastRanges.append(copyPastRanges[-1] + r - l + 1)
	for i in range(q):
		k = int(input())
		while True:
			for j in range(len(copyPastRanges)):
				if copyPastRanges[j] >= k:
					(l, r) = copyPastINtervals[j]
					d = copyPastRanges[j] - k
					k = r - d
					break
			if k <= n:
				break
		print(a[k % n - 1])


def query(s, d, x):
	if x < len(s):
		return s[x]
	for i in d:
		j = d[i]
		if i + j[-1] > x:
			return query(s, d, x - i + j[0])
for t in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	d = {}
	for i in [1] * c:
		(x, y) = map(int, input().split())
		d[n] = [x - 1, y - 1, y - x + 1]
		n += y - x + 1
	for i in [1] * q:
		x = int(input()) - 1
		print(query(s, d, x))


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	w = input()
	w_len = len(w)
	changes = []
	for x in range(c):
		(a, b) = map(int, input().split())
		w_len += b - a + 1
		changes.append([a, b, w_len])
	for y in range(q):
		found_ans = False
		query = int(input())
		if query <= n:
			print(w[query - 1])
			continue
		while query > n:
			for xx in range(len(changes)):
				if changes[xx][2] >= query:
					query = changes[xx][1] - (changes[xx][2] - query)
					break
			if query <= n:
				ans = query
				found_ans = True
				break
		print(w[ans - 1])


def find(s, d, x):
	if x < len(s):
		return s[x]
	for i in d:
		j = d[i]
		if x < i + j[-1]:
			return find(s, d, x - i + j[0])
for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	d = {}
	l = len(s)
	for i in range(c):
		(x, y) = map(int, input().split())
		d[l] = [x - 1, y - 1, y - x + 1]
		l += y - x + 1
	for Q in range(q):
		x = int(input()) - 1
		print(find(s, d, x))


t = int(input())

def diff(x):
	return x[1] - x[0]
for i in range(t):
	line = input().split()
	int_line = [int(x) for x in line]
	(n, c, q) = int_line
	text = input()
	c_list = []
	for i in range(c):
		line = input().split()
		int_line = [int(x) for x in line]
		(l, r) = int_line
		l -= 1
		c_list.append((l, r))
	pos_list = [n]
	for i in range(c):
		pos_list.append(pos_list[-1] + diff(c_list[i]))
	for j in range(q):
		pos = int(input()) - 1
		while pos >= n:
			index = 0
			while pos >= pos_list[index + 1]:
				index += 1
			pos = pos - pos_list[index] + c_list[index][0]
		print(text[pos])


for i in range(int(input())):
	(n, c, q) = map(int, input().split())
	a = input()
	intervals = [(1, n)]
	ranges = [n]
	for i in range(c):
		(x, y) = map(int, input().split())
		intervals.append((x, y))
		ranges.append(ranges[-1] + y - x + 1)
	for i in range(q):
		z = int(input())
		while True:
			for j in range(len(ranges)):
				if ranges[j] >= z:
					(x, y) = intervals[j]
					d = ranges[j] - z
					z = y - d
					break
			if z <= n:
				break
		print(a[z - 1])


t = int(input())
while t > 0:
	t -= 1
	(n, c, q) = map(int, input().split())
	string = input()
	queries = [[1, n]]
	quer2 = [[1, n]]
	while c > 0:
		c -= 1
		(a, b) = map(int, input().split())
		tot = quer2[-1][-1]
		quer2.append([tot + 1, tot + 1 + (b - a)])
		queries.append([a, b])
	size = len(quer2)
	while q > 0:
		q -= 1
		k = int(input())
		while k > n:
			for i in range(-1, -(size + 1), -1):
				if quer2[i][0] <= k <= quer2[i][1]:
					break
			m = queries[i][0] + k - quer2[i][0]
			k = m
		print(string[k - 1])


def findLetter(n, indices, x):
	if x <= n:
		return s[x - 1]
	else:
		count = n
		for index in indices:
			count += index[1] - index[0] + 1
			if x <= count:
				a = count - (index[1] - index[0] + 1)
				b = x - a - 1
				newX = index[0] + b
				return findLetter(n, indices, newX)
for _ in range(int(input())):
	(n, c, q) = [int(x) for x in input().split()]
	s = input()
	indices = []
	for i in range(c):
		(l, r) = [int(x) for x in input().split()]
		indices.append((l, r))
	for i in range(q):
		x = int(input())
		print(findLetter(n, indices, x))


t = int(input())
for i in range(t):
	(n, c, q) = map(int, input().split())
	s = input()
	limits = [(1, n)]
	diff = [0]
	for i in range(c):
		(l, r) = map(int, input().split())
		limits.append((limits[-1][1] + 1, limits[-1][1] + 1 + r - l))
		diff.append(limits[-1][1] - r)
	for i in range(q):
		x = int(input())
		while True:
			l = 0
			r = len(diff) - 1
			while l <= r:
				mid = (l + r) // 2
				if x in range(limits[mid][0], limits[mid][1] + 1):
					break
				elif x < limits[mid][0]:
					r = mid - 1
				else:
					l = mid + 1
			if diff[mid] != 0:
				x -= diff[mid]
			else:
				print(s[x - 1])
				break


t = int(input())
for i in range(t):
	(n, c, q) = map(int, input().split())
	s = list(input())
	m = [0]
	dl = [n]
	for x in range(c):
		(l, r) = map(int, input().split())
		m.append(l - 1)
		dl.append(r - l + 1)
	for x in range(q):
		w = int(input()) - 1
		while w >= n:
			for e in range(len(dl)):
				if dl[e] > w:
					st = e
					break
				else:
					w -= dl[e]
			w += m[st]
		print(s[w])


for _ in range(int(input())):
	(n, c, q) = map(int, input().split())
	s = input()
	d = {}
	for i in range(c):
		(x, y) = map(int, input().split())
		d[n] = [x - 1, y - x + 1]
		n += y - x + 1
	for Q in range(q):
		x = int(input()) - 1
		while x >= len(s):
			for i in d:
				j = d[i]
				if x < i + j[-1]:
					x -= i - j[0]
					break
		print(s[x])


t = int(input())
for i in range(t):
	(n, c, q) = map(int, input().split())
	string = input()
	d = {}
	for j in range(c):
		(a, b) = map(int, input().split())
		d[n] = [a - 1, b - a + 1]
		n += b - a + 1
	for k in range(q):
		x = int(input()) - 1
		while x >= len(string):
			for l in d:
				a = d[l]
				if x < l + a[-1]:
					x -= l
					x += a[0]
					break
		print(string[x])


for _ in range(int(input())):
	(n, c, q) = list(map(int, input().split()))
	string = str(input())
	cc = []
	for i in range(c):
		cc.append(list(map(int, input().split())))

	def get_prev_size_and_start_for_index(index):
		if index < n:
			return (0, 0)
		s = n
		for i in range(c):
			add = cc[i][1] - cc[i][0] + 1
			s += add
			if index < s:
				return (s - add, i)

	def get_real_index(index):
		(s, start) = get_prev_size_and_start_for_index(index)
		start = cc[start][0] - 1
		if s == 0:
			return index
		return get_real_index(index - s + start)
	for i in range(q):
		qq = int(input())
		qq -= 1
		print(string[get_real_index(qq)])