Козак Вус прийшов на залізничну дорогу, щоб поїхати на випробування чарівних черевиків і дізнався, що на всьому залізничному шляху проблеми з освітленням. Залізнична дорога має форму великої вісімки, по якій їздить потяг. Місце, де шляхи перетинаються назвемо перехрестям.
Козак Вус хоче виправити проблеми з освітленням. Для цього він придбав n ліхтарів, кожен з яких має колір від 1 до k. Гарантується, що було придбано хоча б по одному ліхтарю кожного кольору. Проблеми з освітленням будуть виправлені, якщо:
Вздовж залізничної дороги буде розміщено n ліхтарів.
Один з ліхтарів стоїть на перехресті.
Якщо два ліхтарі стоять поруч (тобто вони обидва стоять на одній і тій же гілці, а також між ними немає іншого ліхтаря), то вони мають різні кольори.
На верхній і нижній гілках дороги стоять не менше 2-х ліхтарів (не включаючи перехрестя).
Допоможіть Козаку Вусу знайти будь-який спосіб виправити проблеми з освітленням або вкажіть, що його не існує.
Перший рядок містить три цілі числа n, k і g (5≤n≤2⋅105, 1≤k≤2⋅105, 0≤g≤8) — кількість ліхтарів і кольорів відповідно, а також номер блока.
Наступний рядок містить n цілих чисел a1,a2,…,an (1≤ai≤k) — кольори стовпів.
Гарантується, що кожне з чисел від 1 до k присутнє в цьому масиві.
Якщо відповіді немає, то виведіть −1.
Інакше у першому рядку виведіть два числа x і y (2≤x,y<n, 1+x+y=n) — кількість ліхтарів на верхній і нижній гілках не враховуючи перехрестя відповідно.
У другому рядку виведіть x чисел b1,b2,…,bx (1≤bi≤k) — кольори ліхтарів, що стоять на верхній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя.
У третьому рядку виведіть одне число c (1≤c≤k) — колір ліхтаря, що стоїть на перехресті.
У четвертому рядку виведіть y чисел d1,d2,…,dy (1≤di≤k) — кольори ліхтарів, що стоять на нижній гілці в порядку обходу по годинниковій стрілці, починаючи з першого ліхтаря після перехрестя.
Якщо відповідей кілька, то можете вивести будь-яку.
Вважайте, що ліхтар на перехресті стоїть на обох гілках одночасно.
У першому прикладі можемо поставити два ліхтарі з кольорами 1 і 2 на верхню гілку, два ліхтарі з кольорами 1 і 2 на нижню гілку і ліхтар з кольором 3 на перехрестя. Таким чином кожні два сусідні ліхтарі будуть різних кольорів.
Другий приклад зображений на малюнку вище.
У третьому прикладі Козаку Вусу не вдасться виправити проблеми з освітленням, адже при будь-якій розстановці знайдуться два сусідні ліхтарі кольору 1.
(8 балів): n≤8.
(20 балів): n — парне, один з кольорів буде зустрічатися рівно 2n рази, n≤1000.
(5 балів): n=k, n≤1000.
(8 балів): n≤18; k=2.
(10 балів): k=2, n≤1000.
(14 бали): k=2, n≤1000.
(20 балів): n≤1000.
(15 балів): без додаткових обмежень.