Козак Вус та залізнична дорога

Козак Вус прийшов на залізничну дорогу, щоб поїхати на випробування чарівних черевиків і дізнався, що на всьому залізничному шляху проблеми з освітленням. Залізнична дорога має форму великої вісімки, по якій їздить потяг. Місце, де шляхи перетинаються назвемо перехрестям.

Козак Вус хоче виправити проблеми з освітленням. Для цього він придбав $n$ ліхтарів, кожен з яких має колір від $1$ до $k$. Гарантується, що було придбано хоча б по одному ліхтарю кожного кольору. Проблеми з освітленням будуть виправлені, якщо:

1. Вздовж залізничної дороги буде розміщено $n$ ліхтарів.

2. Один з ліхтарів стоїть на перехресті.

3. Якщо два ліхтарі стоять поруч (тобто вони обидва стоять на одній і тій же гілці, а також між ними немає іншого ліхтаря), то вони мають різні кольори.

4. На верхній і нижній гілках дороги стоять не менше 2-х ліхтарів (не включаючи перехрестя).

Допоможіть Козаку Вусу знайти будь-який спосіб виправити проблеми з освітленням або вкажіть, що його не існує.

Giriş verilənləri

Перший рядок містить три цілі числа $n$, $k$ і $g$ ($5\le n\le 2\cdot 10^5$, $1\le k\le 2\cdot 10^5$, $0\le g\le 8$) — кількість ліхтарів і кольорів відповідно, а також номер блока.

Наступний рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($1\le a_i\le k$) — кольори стовпів.

Гарантується, що кожне з чисел від $1$ до $k$ присутнє в цьому масиві.

Çıxış verilənləri

Якщо відповіді немає, то виведіть $-1$.

Інакше у першому рядку виведіть два числа $x$ і $y$ ($2\le x,y<n$, $1+x+y=n$) — кількість ліхтарів на верхній і нижній гілках не враховуючи перехрестя відповідно.

У другому рядку виведіть $x$ чисел $b_1,b_2,\dots ,b_x$ ($1\le b_i\le k$) — кольори ліхтарів, що стоять на верхній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя.

У третьому рядку виведіть одне число $c$ ($1\le c\le k$) — колір ліхтаря, що стоїть на перехресті.

У четвертому рядку виведіть $y$ чисел $d_1,d_2,\dots ,d_y$ ($1\le d_i\le k$) — кольори ліхтарів, що стоять на нижній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя.

Якщо відповідей кілька, то можете вивести будь-яку.

Nümunələr

Qeyd

Вважайте, що ліхтар на перехресті стоїть на обох гілках одночасно.

У першому прикладі можемо поставити два ліхтарі з кольорами $1$ і $2$ на верхню гілку, два ліхтарі з кольорами $1$ і $2$ на нижню гілку і ліхтар з кольором $3$ на перехрестя. Таким чином кожні два сусідні ліхтарі будуть різних кольорів.

Другий приклад зображений на малюнку вище.

У третьому прикладі Козаку Вусу не вдасться виправити проблеми з освітленням, адже при будь-якій розстановці знайдуться два сусідні ліхтарі кольору $1$.

Qiymətləndirmə

1. ($8$ балів): $n\le 8$.

2. ($20$ балів): $n$ — парне, один з кольорів буде зустрічатися рівно $\frac{n}{2}$ рази, $n\le 1000$.

3. ($5$ балів): $n=k$, $n\le 1000$.

4. ($8$ балів): $n\le 18$; $k=2$.

5. ($10$ балів): $k=2$, $n\le 1000$.

6. ($14$ бали): $k\ne 2$, $n\le 1000$.

7. ($20$ балів): $n\le 1000$.

8. ($15$ балів): без додаткових обмежень.