Алиса и Боб играют в Лужаньци. У каждого из них есть перестановка из следующих 24 фигур:

• один Фельдмаршал, ранг 9
• один Генерал, ранг 8
• два Генерал-майора, ранг 7
• два Бригадных генерала, ранг 6
• два Полковника, ранг 5
• два Майора, ранг 4
• три Капитана, ранг 3
• три Лейтенанта, ранг 2
• три Инженера, ранг 1
• две Бомбы
• три Мины

Чтобы определить победителя, мы повторяем следующий процесс, пока кто-то не выиграет или игра не закончится вничью:

• Если обе перестановки пусты, игра заканчивается вничью.
• Если перестановка Алисы пуста, Боб выигрывает игру.
• Если перестановка Боба пуста, Алиса выигрывает игру.

• Пусть первая фигура в перестановке Алисы — $A$, а первая фигура в перестановке Боба — $B$. Результат битвы между $A$ и $B$ определяется следующим образом:

• Если $A$ и $B$ — фигуры одного типа, или если одна из фигур $A$ или $B$ — Бомба, обе они удаляются.

• В противном случае, если одна из фигур $A$ или $B$ — Мина, а другая — Инженер, Мина удаляется, а Инженер остается в игре.
• В противном случае, если одна из фигур $A$ или $B$ — Мина, а ранг другой фигуры больше 1, Мина остается в игре, а другая фигура удаляется.
• В противном случае мы сравниваем ранги $A$ и $B$, и фигура с меньшим рангом удаляется.

Боб заранее знает перестановку Алисы и может определить свою перестановку на основе этой информации. После того как Боб определит свою перестановку, Алиса может поменять местами две фигуры в перестановке Боба. Может ли Боб составить такую перестановку, которая выигрывает у перестановки Алисы независимо от того, какую пару фигур она поменяет местами?

Входные данные

Первая строка содержит одно целое число $T$, обозначающее количество тестовых случаев ($1 \le T \le 100$). Каждая из следующих $T$ строк содержит 24 целых числа, обозначающих перестановку Алисы:

• 40 представляет Фельдмаршала
• 39 представляет Генерала
• 38 представляет Генерал-майоров
• 37 представляет Бригадных генералов
• 36 представляет Полковников
• 35 представляет Майоров
• 34 представляет Капитанов
• 33 представляет Лейтенантов
• 32 представляет Инженеров
• 31 представляет Мины
• 30 представляет Бомбы

Гарантируется, что все перестановки выбираются равномерно случайным образом и содержат ровно 24 фигуры, описанные в условии.

Выходные данные

Выведите по одной строке для каждого тестового случая. Если Боб не может составить требуемую перестановку, выведите $-1$. В противном случае выведите 24 целых числа, представляющих перестановку Боба в том же формате, что и во входных данных. Если существует несколько решений, выведите любое. Перестановка Боба должна содержать ровно 24 фигуры, описанные в условии.

Примеры

Входные данные 1

4
40 39 38 38 37 37 36 36 35 35 34 34 34 33 33 33 32 32 32 31 31 31 30 30
34 31 36 33 31 39 37 38 35 32 32 35 36 31 34 32 38 40 30 33 30 34 33 37
37 30 40 38 36 38 32 34 36 35 37 32 34 33 31 30 33 31 35 34 33 39 31 32
30 33 32 39 37 38 35 40 34 30 31 37 31 33 31 33 34 32 36 36 35 34 32 38

Выходные данные 1

34 36 30 39 33 38 37 31 34 30 33 35 38 31 37 33 40 31 35 32 32 36 32 34
34 32 32 38 40 33 33 30 31 34 31 35 37 32 34 36 33 31 38 30 36 37 35 39
38 33 32 31 36 34 30 34 33 40 32 37 38 30 37 35 33 35 32 31 34 31 39 36
37 34 33 36 34 35 31 38 32 38 31 32 37 30 30 31 33 36 32 33 40 39 34 35