Хомяк Шустрик и ёжик Шуршик проводят рискованный эксперимент.
У них есть $$$n$$$ магических кристаллов, каждый с целочисленным уровнем энергии. Кристаллы нужно разложить по двум камерам для дальнейших наблюдений. Дабы эксперимент не был провальным, должно соблюдаться правило: два кристалла, чьи энергии в сумме дают простое число, не должны находиться в одной камере.
Помогите хомяку и ёжику найти такое распределение кристаллов по двум камерам, чтобы ни одна пара кристаллов не нарушала описанного правила.
Шустрик и Шуршик напоминают, что простым числом называется натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя.
В первой строке ввода содержится целое число $$$n$$$ — количество магических кристаллов ($$$1 \le n \le 10^5$$$).
Во второй строке ввода содержится $$$n$$$ целых чисел $$$a_i$$$ — энергии всех магических кристаллов ($$$2 \le a_i \le 10^{12}$$$).
Если невозможно распределить кристаллы по двум камерам с соблюдением описанного правила, то в единственной строке выведите $$$-1 -1$$$ (два числа минус один, разделённые пробелом). Если распределить кристаллы возможно, то:
В первой строке выведите числа $$$n_1$$$ и $$$n_2$$$ — количество кристаллов в первой и второй камерах соответственно.
Во второй строке выведите в любом порядке энергии магических кристаллов из первой камеры, разделяя элементы пробелом.
В третьей строке выведите в любом порядке энергии магических кристаллов из второй камеры, также разделяя элементы пробелом.
Если существует несколько распределений, выведите любое из них.
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы, всех тестов необходимых для неё групп и тестов из условия.
| Группа | Баллы | Доп. ограничения | |
| 1 | 20 | $$$n \le 10, a_i \le 100$$$ | – |
| 2 | 15 | $$$n \le 200, a_i \le 200$$$ | 1 |
| 3 | 20 | $$$n \le 200, a_i \le 3 \cdot 10^6$$$ | 1, 2 |
| 4 | 15 | $$$n \le 3\,000, a_i \le 3 \cdot 10^6$$$ | 1, 2, 3 |
| 5 | 5 | $$$n \le 10\,000, a_i \le 5 \cdot 10^7$$$ | 1–4 |
| 6 | 10 | $$$a_i \le 10^9$$$ | 1–5 |
| 7 | 15 | – | 1–6 |
22 3
1 1 2 3
67 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)$$$.
