Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Bear and Two Paths

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBearland has *n* cities, numbered 1 through *n*. Cities are connected via bidirectional roads. Each road connects two distinct cities. No two roads connect the same pair of cities.

Bear Limak was once in a city *a* and he wanted to go to a city *b*. There was no direct connection so he decided to take a long walk, visiting each city exactly once. Formally:

- There is no road between
*a*and*b*. - There exists a sequence (path) of
*n*distinct cities*v*_{1},*v*_{2}, ...,*v*_{n}that*v*_{1}=*a*,*v*_{n}=*b*and there is a road between*v*_{i}and*v*_{i + 1}for .

On the other day, the similar thing happened. Limak wanted to travel between a city *c* and a city *d*. There is no road between them but there exists a sequence of *n* distinct cities *u*_{1}, *u*_{2}, ..., *u*_{n} that *u*_{1} = *c*, *u*_{n} = *d* and there is a road between *u*_{i} and *u*_{i + 1} for .

Also, Limak thinks that there are at most *k* roads in Bearland. He wonders whether he remembers everything correctly.

Given *n*, *k* and four distinct cities *a*, *b*, *c*, *d*, can you find possible paths (*v*_{1}, ..., *v*_{n}) and (*u*_{1}, ..., *u*_{n}) to satisfy all the given conditions? Find any solution or print -1 if it's impossible.

Input

The first line of the input contains two integers *n* and *k* (4 ≤ *n* ≤ 1000, *n* - 1 ≤ *k* ≤ 2*n* - 2) — the number of cities and the maximum allowed number of roads, respectively.

The second line contains four distinct integers *a*, *b*, *c* and *d* (1 ≤ *a*, *b*, *c*, *d* ≤ *n*).

Output

Print -1 if it's impossible to satisfy all the given conditions. Otherwise, print two lines with paths descriptions. The first of these two lines should contain *n* distinct integers *v*_{1}, *v*_{2}, ..., *v*_{n} where *v*_{1} = *a* and *v*_{n} = *b*. The second line should contain *n* distinct integers *u*_{1}, *u*_{2}, ..., *u*_{n} where *u*_{1} = *c* and *u*_{n} = *d*.

Two paths generate at most 2*n* - 2 roads: (*v*_{1}, *v*_{2}), (*v*_{2}, *v*_{3}), ..., (*v*_{n - 1}, *v*_{n}), (*u*_{1}, *u*_{2}), (*u*_{2}, *u*_{3}), ..., (*u*_{n - 1}, *u*_{n}). Your answer will be considered wrong if contains more than *k* distinct roads or any other condition breaks. Note that (*x*, *y*) and (*y*, *x*) are the same road.

Examples

Input

7 11

2 4 7 3

Output

2 7 1 3 6 5 4

7 1 5 4 6 2 3

Input

1000 999

10 20 30 40

Output

-1

Note

In the first sample test, there should be 7 cities and at most 11 roads. The provided sample solution generates 10 roads, as in the drawing. You can also see a simple path of length *n* between 2 and 4, and a path between 7 and 3.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/16/2018 03:36:33 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|