Дитячий дует

Limits: 1 sec., 256 MiB

Арсеній та Юля мають змогу виграти цілу торбу цукерок від вчителя математики якщо зможуть виконати його завдання. Вчитель має набір карточок з різними числами. Спочатку Арсеній бере деякі з цих чисел собі, а потім Юля бере собі деякі з тих котрі залишились. Кожен повинен взяти як мінімум одну карточку. Потім Арсеній та Юля рахують суму чисел на своїх карточках і якщо в цих сум є хоча б один спільний дільник більший за одиницю то вони отримують цукерки. Вчитель добрий, тому спосіб отримати цукерки існуватиме завжди — допоможіть дітям зрозуміти як. Якщо є декілька способів досягнути мети, ви можете обрати довільний з них.

Input

Перша стрічка містить одне число \(n\) — кількість карточок. Друга стрічка містить \(n\) чисел через пробіл — числа на карточках.

Output

В першій стрічці через пробіл виведіть два числа \(k, l\) — кількість карточок які повинні взяти Арсен та Юля відповідно. В другому рядку виведіть \(k\) чисел — карточки які обрав Арсен. В третьому рядку виведіть \(l\) чисел — карточки які обрала Юля.

Constraints

\(4 \leq n \leq 1000\),

Кожне з чисел на карточках від \(1\) до \(10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 19 7 11 31 99 13 17	3 3 7 11 17 31 13 19

Input (stdin) сopy	Output (stdout) сopy
4 4 7 17 17	1 1 17 17

Notes

В першому тесті ми отримуємо суми 35 та 63 — обидві діляться на 7. В другому тесті є два однакові числа більші за одиницю, отже вони обидва діляться самі на себе.