A. Вместе мы сила
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$, содержащий целые числа. Также есть два изначально пустых массива $$$b$$$ и $$$c$$$. Вам нужно каждый элемент массива $$$a$$$ добавить ровно в один из массивов $$$b$$$ или $$$c$$$, чтобы выполнялись следующие условия:

  • Каждый из массивов $$$b$$$ и $$$c$$$ непустой. Более формально, пусть $$$l_b$$$ — длина массива $$$b$$$, $$$l_c$$$ — длина массива $$$c$$$. Тогда $$$l_b, l_c \ge 1$$$.
  • Для любых двух индексов $$$i$$$ и $$$j$$$ ($$$1 \le i \le l_b, 1 \le j \le l_c$$$) число $$$c_j$$$ не является делителем $$$b_i$$$.

Выведите массивы $$$b$$$ и $$$c$$$, которые могут получиться, или выведите $$$-1$$$, если их не существует.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 100$$$) — длину массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

Для каждого набора входных данных выведите одно целое число $$$-1$$$, если решения не существует.

Иначе, в первой строке выведите два целых числа $$$l_b$$$ и $$$l_c$$$ — длины массивов $$$b$$$ и $$$c$$$ соответственно.

Во второй строке выведите $$$l_b$$$ целых чисел $$$b_1, b_2, \ldots, b_{l_b}$$$ — элементы массива $$$b$$$.

В третьей строке выведите $$$l_c$$$ целых чисел $$$c_1, c_2, \ldots, c_{l_c}$$$ — элементы массива $$$c$$$.

Если существует несколько возможных решений, выведите любое из них. Элементы массивов можно выводить в любом порядке.

Пример
Входные данные
5
3
2 2 2
5
1 2 3 4 5
3
1 3 5
7
1 7 7 2 9 1 4
5
4 8 12 12 4
Выходные данные
-1
3 2
1 3 5 
2 4 
1 2
1 
3 5 
2 5
1 1 
2 4 7 7 9 
3 2
4 8 4 
12 12
Примечание

В первом наборе входных данных решения не существует.

Во втором наборе входных данных мы можем получить $$$b = [1, 3, 5]$$$ и $$$c = [2, 4]$$$. Тогда элементы $$$2$$$ и $$$4$$$ не делят элементы $$$1, 3$$$ и $$$5$$$.

В пятом наборе входных данных мы можем получить $$$b = [4, 8, 4]$$$ и $$$c = [12, 12]$$$.