Підчисло

Петрик та Василько — справжні друзі, тому вони постійно задають один одному всілякі цікаві задачі. Проте Василько завжди з легкістю розв’язує задачі свого друга, тож Петрик вирішив придумати по-справжньому складну задачу. І ось що в нього вийшло.

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

Задано $N$-цифрове число $X$. Позначимо як $X_K$ найбільше $K$-цифрове підчисло числа $X$. Необхідно відповісти на $M$ запитів. Кожен запит складається з двох чисел — $K$ і $L$. Відповіддю на запит є $L$-та цифра числа $X_K$.

Цього разу задача справді змусила Василька задуматись. А чи зможете ви розв’язати її швидше за нього?

Завдання

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

Вхідні дані

У першому рядку вхідного файла міститься ціле число $X$ довжини $N$ ($1\le N\le 10^5$).

У другому рядку міститься число $M$ ($1\le M\le 10^5$).

У наступних $M$ рядках міститься по два числа $K_i$, $L_i$ ($1\le K_i\le N$,$1\le L_i\le K_i$) — параметри $i$-го запиту.

Вихідні дані

Вихідний файл повинен містити один рядок довжини $M$, в якому $i$-й символ є відповіддю на $i$-й запит.

Приклади

Оцінювання

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

1. ($15$ балів): $N=20$; $M=10000$;

2. ($25$ балів): $N\times M\le 500000$;

3. ($60$ балів): $N\le 100000$; $M\le 50000$.