B. Медвежонок и два пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Беарляндии n городов, пронумерованных целыми числами от 1 до n. Города соединены двусторонними дорогами. Никакая дорога не соединяет город с самим собой, и никакая пара городов не соединена больше чем одной дорогой.

Однажды медвежонок Лимак оказался в городе a и захотел пойти в город b. Между ними не было прямой дороги, поэтому он решил прогуляться и посетить каждый город ровно один раз. Формально:

  • Не существует дороги между городами a и b.
  • Существует путь, состоящий из n различных городов v1, v2, ..., vn, такой что v1 = a, vn = b, а города vi и vi + 1 соединены дорогой при .

На другой день ситуация повторилась. Лимак находился в городе c и хотел отправиться в город d, но дороги между ними не было, поэтому он решил прогуляться по длинному пути из n различных городов u1, u2, ..., un, такому что u1 = c, un = d, и между ui и ui + 1 есть дорога для .

Лимак полагает, что в Беарляндии не более k дорог, и просит вас проверить, может ли так быть, что он всё помнит правильно. По данным n, k и четырём различным индексам городов a, b, c и d, восстановите два пути (v1, ..., vn) и (u1, ..., un), которые удовлетворят всем условиям, или определите, что это невозможно.

Входные данные

В первой строке входных данных записаны два числа n и k (4 ≤ n ≤ 1000, n - 1 ≤ k ≤ 2n - 2) — количество городов и максимально допустимое количество дорог соответственно.

Во второй строке записаны четыре различных числа a, b, c и d (1 ≤ a, b, c, d ≤ n).

Выходные данные

Если выполнить все условия невозможно, то выведите -1 в единственной строке выходных данных. В противном случае выведите две строки с описанием путей.

Первая из них должна содержать n различных индексов городов v1, v2, ..., vn, и при этом должно выполняться v1 = a и vn = b. Вторая строка аналогично содержит n различных индексов u1, u2, ..., un, описывающих второй путь, то есть должно выполняться u1 = c и un = d.

Эти два пути определяют не более чем 2n - 2 дорог: (v1, v2), (v2, v3), ..., (vn - 1, vn), (u1, u2), (u2, u3), ..., (un - 1, un). Ваш ответ будет считаться неправильным, если различных дорог будет больше k или будет нарушено какое-то другое условие.

Обратите внимание, что (x, y) и (y, x) обозначают одну и ту же дорогу.

Примеры
Входные данные
7 11
2 4 7 3
Выходные данные
2 7 1 3 6 5 4
7 1 5 4 6 2 3
Входные данные
1000 999
10 20 30 40
Выходные данные
-1
Примечание

В первом примере должно быть 7 городов и не более 11 дорог. В представленном решении содержится 10 дорог, как на картинке. Также показаны простые пути длины n между 2 и 4 и между 7 и 3.