Козак Вус та залізнична дорога

Вхідні дані

Перший рядок містить три цілі числа $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$ і $2$ на верхню гілку, два ліхтарі з кольорами $1$ і $2$ на нижню гілку і ліхтар з кольором $3$ на перехрестя. Таким чином кожні два сусідні ліхтарі будуть різних кольорів.

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

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

Оцінювання

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$ балів): без додаткових обмежень.