Being encouraged by XOR operation of binary numbers, Nanna Munna has decided to make a new kind of digit-wise operations for decimal numbers. He named this operation Decimation, $DON$ in short.
For two digits $A$ and $B$, $A \; DON \; B$ is defined as $fun(A+B)$ where $fun$ is a function defined as the below pseudocode.
fun(n)
{
if (n < 10) return n;
return fun(sum of all digits of n);
}
Basically, $fun$ is a recursive function that sums the digits of a number to get a new number, and if that number is not a digit, the fun of that number is recursively called. For example, $fun(888) = fun(24) = fun(6) = 6$ and similarly $fun(14) = fun(5) = 5$.
For two decimal numbers $X$ and $Y$, $X \; DON \; Y = Z$
where $Z_i = X_i \; DON \; Y_i$ and $X_i$, $Y_i$, $Z_i$ represent the i-th digit of $X$, $Y$, $Z$ respectively (from right hand side).
For example, $484 \; DON \; 5823 = 5317$ since
for 0th digit, $4 \; DON \; 3 = 7$
for 1st digit, $8 \; DON \; 2 = 1$
for 2nd digit, $4 \; DON \; 8 = 3$
for 3rd digit, $0 \; DON \; 5 = 5$
In this problem, you will be given an array $A$ of $N$ integers. You will be then given $Q$ queries. For each query $X \; K$, you have to find all the numbers $A_i \; DON X$ (where $1 \leq i \leq N$) and print the $K$-th smallest number from among them.
Input
In the first line of input, $N$ and $Q$ will be given.
In the following line, $N$ integers will be given to represent the array $A$.
In each of the next $Q$ lines, two integers $X$ and $K$ will be given representing a query.
Constraints
$ 1 \leq N, Q, A_i, X \leq 10^5 $$ 1 \leq K \leq N $
It is guaranteed that the digit $9$ will not exist in $A_i$ or $X$ i.e. no element of the array $A$ or no $X$ of any query will contain the digit $9$.
Output
For each query, print the answer in a separate line as shown in sample I/O.
Sample
| Input | Output |
|---|---|
4 8 1 23 10 7 3 1 3 2 3 3 3 4 88 1 88 2 88 3 88 4 | 1 4 13 26 12 86 89 98 |
When | |
