Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым
количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать
является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает
эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет
\(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.
После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\)
шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть.
Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только
\(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может
предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\)
ходов прежде, чем Беси надоест, и она перестанет играть.
Можете ли Вы определить лексикографически минимальную последовательность
ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит целое число
\(T\) (
\(1 \leq T \leq 10\)) представляющее
количество подтестов. Каждый подтест описывается следующим образом:
- Сначала идёт строка, содержащая три целых числа \(N\), \(M\), \(K\),
представляющая количество шариков у Эльзы, количество ходов, и количество
потенциальных ходов, которые может сделать Беси, соответственно.
- Затем идут \(M\) строк, где строка \(i\) содержит \(K\) различных
разделённых одиночными пробелами целых чисел
\(a_{i,1} \; a_{i,2} \ldots a_{i,K}\) (\(1 \leq a_{i, j} \leq 10^3\))
представляющих возможные количества шариков, которые Беси может выложить
на \(i\)-ом ходу.
Гарантируется. что сумма
\(M\) по всем подтестам не более
\(3 \cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста выведите лексикографически минимальную последовательность
ходов Эльзы, которая гарантирует, что Эльза не проиграет или
\(-1\), если Эльза
проиграет. Последовательность ходов должна быть на одной строке и состоять из
разделённых одиночными пробелами токенов, каждый из которых равен либо
"Even" либо "Odd".
Замечание: "Even" лексикографически меньше чем "Odd".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|