Петрик та Василько — справжні друзі, тому вони постійно задають один одному всілякі цікаві задачі. Проте Василько завжди з легкістю розв’язує задачі свого друга, тож Петрик вирішив придумати по-справжньому складну задачу. І ось що в нього вийшло. Будемо називати число B підчислом числа A, якщо з числа A можна викреслити деякі цифри так, що цифри, які залишилися, утворюють число B. Задано N-цифрове число X. Позначимо як XK найбільше K-цифрове підчисло числа X. Необхідно відповісти на M запитів. Кожен запит складається з двох чисел — K і L. Відповіддю на запит є L-та цифра числа XK. Цього разу задача справді змусила Василька задуматись. А чи зможете ви розв’язати її швидше за нього?

Завдання

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

Вхідні дані

У першому рядку вхідних даних міститься ціле число X довжини N(1 ≤ N ≤ 105). У другому рядку міститься число M(1 ≤ M ≤ 105). У наступних M рядках міститься по два числа Ki, Li(1 ≤ Ki ≤ N, 1 ≤ Li ≤ Ki) — параметри i-го запиту.

Вихідні дані

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

Оцінювання

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

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

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

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