Подчисло

Петрик и Василько — настоящие друзья, и они постоянно придумывают друг для друга всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил создать по-настоящему сложную задачу. Вот что у него получилось.

Число B будем называть подчислом числа A, если из числа A можно вычеркнуть некоторые цифры так, что оставшиеся цифры образуют число B.

Дано N-значное число X. Обозначим как X[K] наибольшее K-значное подчисло числа X. Необходимо ответить на M запросов. Каждый запрос состоит из двух чисел — K и L. Ответом на запрос является L-я цифра числа X[K].

На этот раз задача действительно заставила Василька задуматься. А сможете ли вы решить её быстрее него?

Задача

Напишите программу subnumber, которая по заданному числу и последовательности запросов найдет необходимые цифры.

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

В первой строке входных данных содержится целое число X длины N (1 ≤ N ≤ 10^5). Во второй строке содержится число M (1 ≤ M ≤ 10^5). В следующих M строках содержится по два числа K[i], L[i] (1 ≤ K[i] ≤ N, 1 ≤ L[i] ≤ K[i]) — параметры i-го запроса.

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

Выходные данные должны содержать одну строку длины M, в которой i-й символ является ответом на i-й запрос.

Примеры

Оценивание

Набор тестов состоит из 3 блоков, для которых дополнительно выполняются такие условия:

1. 15 % баллов: N = 20, M = 10000.

2. 25 % баллов: N×M ≤ 500000.

3. 60 % баллов: N ≤ 100000, M ≤ 50000.