Bear and Two Paths

Bearland 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 = av 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 = cu 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 nk and four distinct cities abcd, 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 ≤ 2n - 2) — the number of cities and the maximum allowed number of roads, respectively.

The second line contains four distinct integers abc 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 2n - 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.

Solution:

#include <bits/stdc++.h>

using namespace std;

int main() {
int n, k;
int a, b, c, d;
scanf("%d %d", &n, &k);
scanf("%d %d %d %d", &a, &b, &c, &d);
if (n == 4 || k <= n) {
    printf("%d\n", -1);
    return 0;
  }

  vector <int> z;
for (int i = 1; i <= n; i++) {
    if (i != a && i != b && i != c && i != d) {
      z.push_back(i);
    }
  }

  int x = z.back();
  z.pop_back();

  printf("%d", a);
  for (int i = 0; i < (int) z.size(); i++) {
    printf(" %d", z[i]);
  }
  printf(" %d %d %d %d\n", c, x, d, b);

  printf("%d", c);
  for (int i = (int) z.size() - 1; i >= 0; i--) {
printf(" %d", z[i]);
}
printf(" %d %d %d %d\n", a, x, b, d);

return 0;
}