Дан массив \(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\), если их не существует.
Выходные данные
Для каждого набора входных данных выведите одно целое число \(-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\).
Если существует несколько возможных решений, выведите любое из них. Элементы массивов можно выводить в любом порядке.
Примечание
В первом наборе входных данных решения не существует.
Во втором наборе входных данных мы можем получить \(b = [1, 3, 5]\) и \(c = [2, 4]\). Тогда элементы \(2\) и \(4\) не делят элементы \(1, 3\) и \(5\).
В пятом наборе входных данных мы можем получить \(b = [4, 8, 4]\) и \(c = [12, 12]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|