Козак Вус прийшов на залізничну дорогу, щоб поїхати на випробування чарівних черевиків і дізнався, що на всьому залізничному шляху проблеми з освітленням. Залізнична дорога має форму великої вісімки, по якій їздить потяг. Місце, де шляхи перетинаються назвемо перехрестям.
Козак Вус хоче виправити проблеми з освітленням. Для цього він придбав $$$n$$$ ліхтарів, кожен з яких має колір від $$$1$$$ до $$$k$$$. Гарантується, що було придбано хоча б по одному ліхтарю кожного кольору. Проблеми з освітленням будуть виправлені, якщо:
- Вздовж залізничної дороги буде розміщено $$$n$$$ ліхтарів.
- Один з ліхтарів стоїть на перехресті.
- Якщо два ліхтарі стоять поруч (тобто вони обидва стоять на одній і тій же гілці, а також між ними немає іншого ліхтаря), то вони мають різні кольори.
- На верхній і нижній гілках дороги стоять не менше 2-х ліхтарів (не включаючи перехрестя).
Допоможіть Козаку Вусу знайти будь-який спосіб виправити проблеми з освітленням або вкажіть, що його не існує.
Перший рядок містить три цілі числа $$$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$$$ присутнє в цьому масиві.
Якщо відповіді немає, то виведіть $$$-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$$$) — кольори ліхтарів, що стоять на нижній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя.
Якщо відповідей кілька, то можете вивести будь-яку.
- ($$$8$$$ балів): $$$n \leq 8$$$.
- ($$$20$$$ балів): $$$n$$$ — парне, один з кольорів буде зустрічатися рівно $$$\frac{n}{2}$$$ рази, $$$n \leq 1000$$$.
- ($$$5$$$ балів): $$$n = k$$$, $$$n \leq 1000$$$.
- ($$$8$$$ балів): $$$n \leq 18$$$; $$$k = 2$$$.
- ($$$10$$$ балів): $$$k = 2$$$, $$$n \leq 1000$$$.
- ($$$14$$$ бали): $$$k \neq 2$$$, $$$n \leq 1000$$$.
- ($$$20$$$ балів): $$$n \leq 1000$$$.
- ($$$15$$$ балів): без додаткових обмежень.
5 3 0 1 2 3 2 1
2 2 2 1 3 1 2
8 3 0 1 1 1 1 2 2 2 3
5 2 1 2 1 2 1 3 2 1
7 3 0 1 1 1 1 1 2 3
-1
9 2 0 1 1 1 1 1 2 2 2 2
5 3 1 2 1 2 1 2 1 2 1
6 6 0 1 2 3 4 5 6
3 2 6 2 5 1 4 3
Вважайте, що ліхтар на перехресті стоїть на обох гілках одночасно.
У першому прикладі можемо поставити два ліхтарі з кольорами $$$1$$$ і $$$2$$$ на верхню гілку, два ліхтарі з кольорами $$$1$$$ і $$$2$$$ на нижню гілку і ліхтар з кольором $$$3$$$ на перехрестя. Таким чином кожні два сусідні ліхтарі будуть різних кольорів.
Другий приклад зображений на малюнку вище.
У третьому прикладі Козаку Вусу не вдасться виправити проблеми з освітленням, адже при будь-якій розстановці знайдуться два сусідні ліхтарі кольору $$$1$$$.