A number $B$ is a subset of number $A$ if you can delete some digits from number $A$ to the remaining digits from number $B$.

You are given an N-digit number $X$ and $X_K$ is the largest K-digit subtype of the number $X$.

You must answer $M$ queries. Each query consists of two numbers $K$ and $L$. The answer to the query is the $L^{th}$ digit of the number $X_K$.

Input format

• The first line contains an integer $X$ of length $N$.
• The second line contains number $M$.
• The next $M$ lines contain two numbers $K_i$ and $L_i$ denoting the parameters of the $i^{th}$ query.

Output format

The output must contain one line of length $M$ in which the $i^{th}$ character is a response to the $i^{th}$ query.

Constraints

$1 ≤ N ≤ 10^5\\ 1 ≤ M ≤ 10^5\\ 1 ≤ K_i ≤ N\\ 1 ≤ L_i ≤ K_i$