# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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.

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.

`$ 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$`

.

For each query, print the answer in a separate line as shown in sample I/O.

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 |