Козак Вус та залізнична дорога
ліміт часу на тест
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$$$.