Однажды ночью Марк вспомнил, что к завтрашнему дню ему нужно было написать сочинение. Он еще не начинал работу. Чтобы успеть в срок, Марк решил случайным образом скопировать и вставить подстроки из аннотации.
Формально, аннотация представляет собой строку \(s\) начальной длины \(n\). Марк выполнит операцию копирования и вставки \(c\) раз. Каждая операция описывается двумя целыми числами \(l\) и \(r\), что означает, что Марк будет добавлять буквы \(s_l s_{l+1} \ldots s_r\) в конец строки \(s\). Обратите внимание, что после этой операции длина \(s\) увеличивается.
Конечно, Марк должен иметь возможность проанализировать написанное. После окончания копирования Марк задаст \(q\) запросов: по заданному целому \(k\) определите \(k\)-ю букву итоговой строки \(s\).
Выходные данные
Для каждого запроса выведите \(k\)-ю букву конечной строки \(s\).
Примечание
В первом наборе входных данных примера процесс копирования-вставки выглядит следующим образом:
- первым действием является дописывание строки \(\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}}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|