Козак Вус прийшов на залізничну дорогу, щоб поїхати на випробування чарівних черевиків і дізнався, що на всьому залізничному шляху проблеми з освітленням. Залізнична дорога має форму великої вісімки, по якій їздить потяг. Місце, де шляхи перетинаються назвемо перехрестям. \begin {center} \includegraphics[scale = 0.5]{https://static.eolymp.com/content/97/9786297a946c4a80856a2f9b89752209.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$) --- кольори ліхтарів, що стоять на нижній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя. Якщо відповідей кілька, то можете вивести будь-яку. \Note Вважайте, що ліхтар на перехресті стоїть на обох гілках одночасно. У першому прикладі можемо поставити два ліхтарі з кольорами $1$ і $2$ на верхню гілку, два ліхтарі з кольорами $1$ і $2$ на нижню гілку і ліхтар з кольором $3$ на перехрестя. Таким чином кожні два сусідні ліхтарі будуть різних кольорів. Другий приклад зображений на малюнку вище. У третьому прикладі Козаку Вусу не вдасться виправити проблеми з освітленням, адже при будь-якій розстановці знайдуться два сусідні ліхтарі кольору $1$. \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}