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 |