\begin{problem}{Козак Вус та залізнична дорога}{standard input}{standard output}{2 seconds}{256 megabytes}

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

\begin {center}
\includegraphics[scale = 0.5]{illustration.jpg}
\end {center}

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

\begin{enumerate} 
\item Вздовж залізничної дороги буде розміщено $n$ ліхтарів.
\item Один з ліхтарів стоїть на перехресті.
\item Якщо два ліхтарі стоять поруч (тобто вони обидва стоять на одній і тій же гілці, а також між ними немає іншого ліхтаря), то вони мають різні кольори.
\item На верхній і нижній гілках дороги стоять не менше 2-х ліхтарів (не включаючи перехрестя).
\end{enumerate}

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

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

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

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

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

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

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

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

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

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

\Scoring
\begin{enumerate}

\item ($8$ балів): $n \leq 8$.

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

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

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

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

\item ($14$ бали): $k \neq 2$, $n \leq 1000$.

\item ($20$ балів): $n \leq 1000$.

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

\end{enumerate}

\Examples

\begin{example}
\exmpfile{example.01}{example.01.a}%
\exmpfile{example.02}{example.02.a}%
\exmpfile{example.03}{example.03.a}%
\exmpfile{example.04}{example.04.a}%
\exmpfile{example.05}{example.05.a}%
\end{example}

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

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

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

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



\end{problem}

