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

Хомяк Шустрик и ёжик Шуршик проводят рискованный эксперимент.

У них есть $$$n$$$ магических кристаллов, каждый с целочисленным уровнем энергии. Кристаллы нужно разложить по двум камерам для дальнейших наблюдений. Дабы эксперимент не был провальным, должно соблюдаться правило: два кристалла, чьи энергии в сумме дают простое число, не должны находиться в одной камере.

Помогите хомяку и ёжику найти такое распределение кристаллов по двум камерам, чтобы ни одна пара кристаллов не нарушала описанного правила.

Шустрик и Шуршик напоминают, что простым числом называется натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.

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

В первой строке ввода содержится целое число $$$n$$$ — количество магических кристаллов ($$$1 \le n \le 10^5$$$).

Во второй строке ввода содержится $$$n$$$ целых чисел $$$a_i$$$ — энергии всех магических кристаллов ($$$2 \le a_i \le 10^{12}$$$).

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

Если невозможно распределить кристаллы по двум камерам с соблюдением описанного правила, то в единственной строке выведите $$$-1 -1$$$ (два числа минус один, разделённые пробелом). Если распределить кристаллы возможно, то:

В первой строке выведите числа $$$n_1$$$ и $$$n_2$$$ — количество кристаллов в первой и второй камерах соответственно.

Во второй строке выведите в любом порядке энергии магических кристаллов из первой камеры, разделяя элементы пробелом.

В третьей строке выведите в любом порядке энергии магических кристаллов из второй камеры, также разделяя элементы пробелом.

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

Система оценки

Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы, всех тестов необходимых для неё групп и тестов из условия.

ГруппаБаллыДоп. ограничения
120$$$n \le 10, a_i \le 100$$$–
215$$$n \le 200, a_i \le 200$$$1
320$$$n \le 200, a_i \le 3 \cdot 10^6$$$1, 2
415$$$n \le 3\,000, a_i \le 3 \cdot 10^6$$$1, 2, 3
55$$$n \le 10\,000, a_i \le 5 \cdot 10^7$$$1–4
610$$$a_i \le 10^9$$$1–5
715–1–6
Примеры
Входные данные
2
2 3
Выходные данные
1 1
2 
3
Входные данные
6
7 14 30 91 15 74
Выходные данные
3 3
7 14 74
30 91 15
Примечание

В первом примере магические кристаллы с энергиями $$$2$$$ и $$$3$$$ не могут быть в одной камере, так как $$$2 + 3 = 5$$$, а число $$$5$$$ является простым числом.

Во втором примере в качестве ответа может подойти несколько разбиений, в том числе подойдут разбиение на $$$(30, 15)$$$ и $$$(7, 14, 91, 74)$$$ и разбиение на $$$(30, 14, 74)$$$ и $$$(7, 91, 15)$$$.