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