Practice on Toph

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

Decimation Operation

By Zeronfinity · Limits 1s, 512 MB

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

InputOutput
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 $X = 3$,
$A_1 \; DON \; X = 1 \; DON \; 3 = 4$
$A_2 \; DON \; X = 23 \; DON \; 3 = 26$
$A_3 \; DON \; X = 10 \; DON \; 3 = 13$
$A_4 \; DON \; X = 7 \; DON \; 3 = 1$
So, for the first query, $K = 1$ and the 1st smallest number among 4, 26, 13, 1 is 1 and thus 1 is the answer to the first query $3 1$. Similarly, 2nd smallest number is 4, the answer to query $3 2$ is 4.


    Discussion

    Statistics


    25% Solution Ratio

    shefinEarliest, 7M ago

    shefinFastest, 0.4s

    shefinLightest, 1.7 MB

    shefinShortest, 3313B

    Submit

    Login to submit

    Related Contests