Moorbles

문제

Bessie and Elsie are playing a game of Moorbles. The game works as follows: Bessie and Elsie each start out with some amount of marbles. Bessie holds out $AA$ of her marbles in her hoof and Elsie guesses if $AA$ is Even or Odd. If Elsie is correct, she wins the $AA$ marbles from Bessie and if she guesses incorrectly, she loses $AA$ of her marbles to Bessie (if Elsie has less than $AA$ marbles, she loses all her marbles). A player loses when they lose all of their marbles.

After some amount of turns in the game, Elsie has $NN$ $(1\le N\le {10}^9)(1\; \backslash leq\; N\; \backslash leq\; 10^9)$ marbles. She thinks it is hard to win, but she is playing to not lose. After being around Bessie enough, Elsie has a good read on Bessie's habits and recognizes that on turn $ii$, there are only $KK$ $(1\le K\le 4)(1\; \backslash leq\; K\; \backslash leq\; 4)$ different amounts of marbles that Bessie may put out. There are only $MM$ $(1\le M\le 3\cdot {10}^5)(1\; \backslash leq\; M\; \backslash leq\; 3\; \backslash cdot\; 10^5)$ turns before Bessie gets bored and stops playing. Can you identify a lexicographically minimum turn sequence such that Elsie will not lose, regardless of how Bessie plays?

입력

The first line contains a single integer $TT$ ($1\le T\le 101\; \backslash leq\; T\; \backslash leq\; 10$) representing the number of test cases. Each test case is described as follows:

• First, one line containing three integers $NN$, $MM$, and $KK$, representing the number of marbles Elsie has, the number of turns, and the number of potential moves Bessie can make respectively.
• Then, $MM$ lines where line $ii$ contains $KK$ distinct space separated integers $a_{i,1}{a}_{i,2}\dots a_{i,K}a\_\{i,1\}\; a\_\{i,2\}\; \backslash ldots\; a\_\{i,K\}$ ($1\le a_{i,j}\le {10}^{3}1\; \backslash leq\; a\_\{i,\; j\}\; \backslash leq\; 10^3$) representing the possible amounts of marbles that Bessie might play on turn $ii$.

It is guaranteed that the sum of $MM$ over all test cases is at most $3\cdot {10}^{5}3\; \backslash cdot\; 10^5$.

출력

For each test case, output the lexicographically minimum move sequence for Elsie to guarantee not losing, or $-1-1$ if she will lose. The move sequence should be on a single line and consist of $MM$ space-separated tokens each equal to either "Even" or "Odd".

Note: "Even" is lexicographically smaller than "Odd".

2
10 3 2
2 5
1 3
1 3
10 3 3
2 7 5
8 3 4
2 5 6

Even Even Odd
-1

1
20 8 2
3 5
3 5
3 5
3 5
3 5
3 5
3 5
3 5

Even Even Even Odd Even Odd Even Odd