Problem Description

Bessie and Elsie are playing a marble game. The rules of the game are as follows: Both Bessie and Elsie start with a certain number of marbles. Bessie places \( A \) marbles under her hoof, and Elsie guesses whether \( A \) is even or odd. If Elsie guesses correctly, she wins \( A \) marbles from Bessie; if she guesses incorrectly, she loses \( A \) marbles to Bessie (if Elsie has fewer than \( A \) marbles, she loses all her marbles). A player loses when they have no marbles left.

After a certain number of rounds, Elsie has \( N \) (\( 1 \le N \le 10^9 \)) marbles. She feels winning is difficult, but she just wants not to lose. After playing with Bessie for a long time, Elsie has a good understanding of Bessie's habits. She finds that in round \( i \), Bessie might only take \( K \) (\( 1 \le K \le 4 \)) different amounts of marbles. There are only \( M \) (\( 1 \le M \le 3 \cdot 10^5 \)) rounds left before Bessie gets bored and quits the game. Can you find the lexicographically smallest sequence of actions such that no matter how Bessie chooses, Elsie will not lose?

Input Format

The first line of the input contains an integer \( T \) (\( 1 \le T \le 10 \)), the number of test cases. Each test case is described as follows:

• The first line contains three integers \( N \), \( M \), and \( K \), representing the number of marbles Elsie has, the number of rounds, and the number of choices Bessie might make, respectively.
• The next \( M \) lines, the \( i \)-th line contains \( K \) distinct space-separated integers \( a_{i,1} a_{i,2} \ldots a_{i,K} \) (\( 1 \le a_{i,j} \le 10^3 \)), representing the possible amounts of marbles Bessie might take in round \( i \).

The input guarantees that the sum of \( M \) across all test cases does not exceed \( 3 \cdot 10^5 \).

Output Format

For each test case, output the lexicographically smallest sequence of actions that ensures Elsie will not lose, or output \( -1 \) if she will lose. The sequence of actions should be output on one line, containing \( M \) space-separated words, each being either Even (even) or Odd (odd).

Note: Even is lexicographically smaller than Odd.

Sample Input and Output

Input Sample #1

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

Output Sample #1

Even Even Odd
-1

Input Sample #2

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

Output Sample #2

Even Even Even Odd Even Odd Even Odd

Notes

Sample Explanation 1

In the first test case, the only lexicographically smaller sequence of actions is Even Even Even, but Bessie can make Elsie lose by first taking \( 5 \), reducing Elsie's marbles from \( 10 \) to \( 5 \), then taking \( 3 \), reducing Elsie's marbles from \( 5 \) to \( 2 \), and finally taking \( 3 \), which would leave her with no marbles.

If Elsie adopts the correct sequence of actions Even Even Odd, then if Bessie plays the same way, when she takes \( 3 \) at the end, Elsie will win those \( 3 \) marbles, increasing her count to \( 5 \). It can be further proven that as long as Elsie's actions are Even Even Odd, Bessie cannot win all of Elsie's marbles in any other way.

In the second test case, it can be proven that for any sequence of actions Elsie might choose, Bessie has a way to win all of Elsie's marbles.

Test Case Properties

• Test case \( 3 \): \( M \le 16 \).
• Test cases \( 4-6 \): \( M \le 1000 \).
• Test cases \( 7-12 \): No additional restrictions.

见题面 Input 部分

见题面 Output 部分