C. Марк и неоконченное эссе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды ночью Марк вспомнил, что к завтрашнему дню ему нужно было написать сочинение. Он еще не начинал работу. Чтобы успеть в срок, Марк решил случайным образом скопировать и вставить подстроки из аннотации.

Формально, аннотация представляет собой строку $$$s$$$ начальной длины $$$n$$$. Марк выполнит операцию копирования и вставки $$$c$$$ раз. Каждая операция описывается двумя целыми числами $$$l$$$ и $$$r$$$, что означает, что Марк будет добавлять буквы $$$s_l s_{l+1} \ldots s_r$$$ в конец строки $$$s$$$. Обратите внимание, что после этой операции длина $$$s$$$ увеличивается.

Конечно, Марк должен иметь возможность проанализировать написанное. После окончания копирования Марк задаст $$$q$$$ запросов: по заданному целому $$$k$$$ определите $$$k$$$-ю букву итоговой строки $$$s$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 1000$$$) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$c$$$ и $$$q$$$ ($$$1\leq n\leq 2\cdot 10^5$$$, $$$1\leq c\leq 40$$$ и $$$1\leq q\leq 10^4$$$) — длина исходной строки $$$s$$$, количество операций копирования-вставки и количество запросов соответственно.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$. Гарантируется, что $$$s$$$ содержит только строчные латинские буквы.

Следующие $$$c$$$ строк описывают операции копирования-вставки. Каждая строка содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1\leq l\leq r\leq 10^{18}$$$). Гарантируется, что $$$r$$$ не превышает текущей длины $$$s$$$.

Последние $$$q$$$ строк каждого набора входных данных содержат запросы. Каждая строка содержит одно целое число $$$k$$$ ($$$1\leq k\leq 10^{18}$$$). Гарантируется, что $$$k$$$ не превышает длины итоговой строки $$$s$$$.

Гарантируется, что суммы $$$n$$$ и $$$q$$$ по всем наборам входных данных не превосходят $$$2\cdot 10^5$$$ и $$$10^4$$$ соответственно.

Выходные данные

Для каждого запроса выведите $$$k$$$-ю букву конечной строки $$$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
Примечание

В первом наборе входных данных примера процесс копирования-вставки выглядит следующим образом:

  • первым действием является дописывание строки $$$\texttt{mark}$$$, что дает строку $$$\texttt{mark}\color{red}{\texttt{mark}}$$$;
  • вторым действием является дописывание строки $$$\texttt{mar}$$$, что дает строку $$$\texttt{markmark}\color{red}{\texttt{mar}}$$$;
  • третье действие — дописывание строки $$$\texttt{rkmark}$$$, в результате чего получается строка $$$\texttt{markmarkmar}\color{red}{\texttt{rkmark}}$$$.

Во втором наборе входных данных примера процесс копирования-вставки выглядит следующим образом:

  • первое действие — дописывание строки $$$\texttt{re}$$$, что дает строку $$$\texttt{creamii}\color{red}{\texttt{re}}$$$;
  • второе действие — дописывание строки $$$\texttt{ea}$$$, что дает строку $$$\texttt{creamiire}\color{red}{\texttt{ea}}$$$;
  • третье действие — дописывание строки $$$\texttt{reamiire}$$$, что дает строку $$$\texttt{creamiireea}\color{red}{\texttt{reamiire}}$$$.