F. Four Warning
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Cindy's slick shuffling and fancy flourishes have allowed her to successfully sideline as a freelance card dealer. She's going to need some extra assistance for today's client, though, as he is... extremely superstitious.

Cindy has been contacted by Fun-Day Master Franz Chua to assist in fortune-telling by use of some mystical numbered cards. Each mystical card contains a single digit from $$$0$$$ to $$$9$$$. For the fortune-telling, Cindy takes a deck that consists of some number of mystical cards, shuffles it well, and then deals all of its card out in a row, in one straight line. Then, we concatenate the digits from left to right to form a single non-negative integer (possibly with leading zeroes).

If the resulting number is divisible by $$$4$$$, then Fun-Day Master Franz Chua predicts that the client will be cursed to live a boring life for the rest of their days. Otherwise, he predicts that the client will have a wonderful and exciting week!

Of course, Fun-Day Master Franz Chua doesn't actually like handing out ill fortunes—it's bad for business! So, he calls a deck of mystical cards Four-Safe if it is absolutely impossible that the resulting number is divisible by $$$4$$$, no matter how the deck is shuffled and dealt.

In order to test that his hired dealer actually understands his fortune-telling process, Fun-Day Master Franz Chua will only hire Cindy if she can solve the following puzzle.

There are $$$n$$$ chests in Fun-Day Master Franz Chua's studio, labeled from $$$1$$$ to $$$n$$$. Each chest contains some number of mystical cards.

Cindy first selects $$$k$$$ of the chests. Then, using only the mystical cards in those chests, she must choose some of them to assemble a Four-Safe deck. Cindy doesn't have to use all the mystical cards in these chests. The goal is to make as large a Four-Safe deck as possible (i.e. one with the greatest number of mystical cards).

What is the largest possible Four-Safe deck that can be constructed by this process?

Input

The first line of input contains two space-separated integers $$$n$$$ and $$$k$$$.

Then, $$$n$$$ lines of input follow, describing the contents of each chest. The $$$i$$$th chest is described by a string of digits $$$s_i$$$ on the $$$i$$$th line. Each digit of $$$s_i$$$ corresponds to a card in the $$$i$$$th chest with that digit written on it.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq k \leq n \leq 2\times 10^5 \\ \text{Each chest contains at least $1$ card.} \\ \text{There are at most $10^6$ cards in total.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{20} & \text{There are at most $5$ cards in total.} \\ \hline 2 & \mathbf{23} & n \leq 10 \\ \hline 3 & \mathbf{17} & n \leq 15 \\ \hline 4 & \mathbf{19} & n \leq 2000 \\ \hline 5 & \mathbf{21} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Output

First, output a line with $$$k$$$ distinct space-separated integers from $$$1$$$ to $$$n$$$, corresponding to the indices of the chests you selected.

Let $$$m$$$ be the size of your Four-Safe deck. If $$$m = 0$$$, output the string empty. Otherwise, if $$$m \gt 0$$$, output a line containing a string of $$$m$$$ digits, representing the Four-Safe deck that you built. It must be possible to construct this string using only digits from the strings of the chests you selected.

If there are multiple possible answers, any will be accepted, so long as $$$m$$$ is maximized.

Examples
Input
4 2
0004
169
269
7200
Output
2 4
1970
Input
4 4
444
4
4444
4
Output
1 2 3 4
empty
Note

The second sample I/O shows that we are always forced to select exactly $$$k$$$ chests, even if we don't use any of the cards from some (or all) of the chosen chests.