406763: GYM102536 B C.U.P.S.

Taal is erupting; panic ensues, hundreds are fleeing, horses are burning, and another island is forming in the lake (Yellow Lake) inside the island (Volcano Island) inside the lake (Taal Lake) inside the island (Luzon). It looks like the world is ending, but you are unfazed through the crisis. You have no reason to worry, being part of the Craters of Utmost Precedence Society (C.U.P.S) - citizens studying interesting volcano craters since time immemorial. With that, a plan to stop the eruption forms!

Taal threatens to devour Batangas and turn all its citizens into Pompeii and Herculaneum, but with your trusty C.U.P.S. standard issue handbook you figure out that there are $$$n$$$ craters from which lava is flowing from. If left unchecked, these craters will erupt in (also) $$$n$$$ days. Each of the $$$n$$$ craters have one of two states:

• Completely filled with ash (blocked and stable)
• Open and spewing with lava (fiery death abound)

A quick survey of the area gives you the state of each of the $$$n$$$ craters $$$S$$$, with $$$S_i$$$ denoting whether the crater is open or not. The cataclysm threatened by Taal will be neutralized if and only if all craters have been completely filled with ash after at most $$$n$$$ days.

To completely fill the craters, your faithful dog (and best friend - because dog is man's best friend <3) Roro can piss on the craters, turning the lava into ash. To this effect you choose $$$m$$$ craters each day for Roro to visit, which can be different or same every day. However, you realize that he's not the brightest of the bunch: he misinterprets your long-term actions into short-term gains, and will always visit exactly $$$m$$$ (no more, no less) craters each day, even if that crater has already been filled with ash. To make matters worse, Taal's volcanic ash is the main component of Roro's favorite food ashbu! If he arrives at a crater currently filled with ash, he will devour the ash inside the crater, opening it again!

Now, you have to plan your actions properly. Given $$$n$$$, the number of craters to completely fill up and consequently the number of days we have, the number of craters $$$m$$$ Roro visits each day, and the inital state of the craters $$$S$$$, find the commands that completely fills Taal volcano if it is even possible, within $$$n$$$ days, or if it is impossible, say so.

The first line of input contains integer $$$t$$$, the number of test cases. $$$t$$$ test cases follow.

Each test case is composed of two lines. The first line contains two space-separated integers $$$n$$$ and $$$m$$$:

• $$$n$$$: The number of craters in Taal to fill up (and number of days before Taal turns Batangas into a wasteland)
• $$$m$$$: The number of craters Roro will visit each day.

The second line of a test case contains the initial state of each crater $$$S$$$. $$$S$$$ is represented as a binary string, with $$$S_i$$$ either being $$$0$$$ or $$$1$$$:

• $$$S_i = 0$$$: The $$$i$$$th crater is open. Close it!
• $$$S_i = 1$$$: The $$$i$$$th crater is closed. Keep it that way!

Constraints

• $$$1 \le t \le 2500$$$
• $$$1 \le m \le n \le 80$$$

For each test case, do the following:

If it is impossible to stop Taal, output the following exact string in a single line:

"CATACLYSM IMMINENT - TIME TO HOARD FACE MASKS"

(without the quotes).

If there is a way to stop Taal, output the craters Roro needs to visit each day in the following format:

• A line containing the nonnegative integer $$$c$$$ denoting the number of days you and Roro need to stop Taal;
• $$$c$$$ lines, each containing a binary string $$$t$$$: $$$t_i = 1$$$ means Roro visits crater $$$i$$$, and $$$t_i = 0$$$ otherwise.

There may be multiple possible ways to stop Taal within $$$n$$$ days. In that case, output any of the valid solutions.

1
4 2
1100

3
1100
0011
1100

In the first test case, Taal starts with the first two craters open: 1100. We have to find a way to fill all of these craters in at most $$$4$$$ days, choosing $$$2$$$ craters each day. We achieve this by choosing the first two craters on the first day, last two craters on the second day, and the first two craters (again) at the third day. By the end of the third day, all craters will be filled up:

1. 0000 after the first day;
2. 0011 after the second day;
3. 1111 after the third day.