Subnumber#7663
Petryk and Vasylko are great friends who love challenging each other with intriguing problems. Vasylko usually solves these problems with ease, so Petryk decided to create a particularly tough one. Here's the challenge he devised:
A number is considered a subnumber of another number if you can remove some digits from such that the remaining digits form .
You are given an -digit number . Let represent the largest -digit subnumber of . You need to respond to queries. Each query consists of two numbers, and . The answer to each query is the -th digit of the number .
This problem has truly puzzled Vasylko. Can you solve it faster than he can?
Write a program subnumber that, given a number and a series of queries, determines the required digits.
The first line contains an integer with a length of , 1 \leq N \leq 10^5.
The second line contains the integer , 1 \leq M \leq 10^5.
The following lines each contain two integers K_i, L_i — the parameters for the -th query, 1 \leq K_i \leq N, 1 \leq L_i \leq K_i.
Output a single line of length , where the -th character is the answer to the -th query.
Example 1
The test set is divided into blocks with the following additional conditions:
of the points: N = 20, M = 10000.
of the points: N \times M \leq 500000.
of the points: N \leq 100000, M \leq 50000.