Козак Вус та залізнична дорога
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

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

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

  1. Вздовж залізничної дороги буде розміщено $$$n$$$ ліхтарів.
  2. Один з ліхтарів стоїть на перехресті.
  3. Якщо два ліхтарі стоять поруч (тобто вони обидва стоять на одній і тій же гілці, а також між ними немає іншого ліхтаря), то вони мають різні кольори.
  4. На верхній і нижній гілках дороги стоять не менше 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$$$) — кольори ліхтарів, що стоять на нижній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя.

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

Система оцінки

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

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

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

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

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

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

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

  8. ($$$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$$$.