Підчисло
Петрик та Василько — справжні друзі, тому вони постійно задають один одному всілякі цікаві задачі. Проте Василько завжди з легкістю розв’язує задачі свого друга, тож Петрик вирішив придумати по-справжньому складну задачу. І ось що в нього вийшло.Будемо називати число 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 блоків, для яких додатково виконуються такі умови:
15 % балів:
N = 20, M = 10000.25 % балів:
N×M ≤ 500000.60 % балів:
N ≤ 100000, M ≤ 50000.