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 = a, v_{n} = b and there is a road between v_{i} and v_{i} + 1 for $i \in \{1,2, \ldots, n - 1 \}$. 

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 $i \in \{1,2, \ldots, n - 1 \}$.

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 ≤ 2n - 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 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.

 [Image]

Difficulty: interview

Starter code:

Solutions:
def main():
	(n, k) = (int(x) for x in input().split())
	(a, b, c, d) = (int(x) for x in input().split())
	(path1, path2) = solver(n, k, a, b, c, d)
	if path1 == None:
		print(-1)
	else:
		for x in path1:
			print(x, end = ' ')
		print()
		for x in path2:
			print(x, end = ' ')

def solver(n, k, a, b, c, d):
	if k <= n or n == 4:
		return (None, None)
	else:
		path1 = [a, c] + \
		[i for i in range(1, n + 1) if i not in (a, b, c, d)] + \
		[d, b]
		path2 = [c, a] + \
		[i for i in range(1, n + 1) if i not in (a, b, c, d)] + \
		[b, d]
		return (path1, path2)

main()
#print(solver(7, 11, 2, 4, 7, 3))

# def reorder(path, n, a, b, c, d):
# 	for i in range(len(path)):
# 		if path[i] == a:
# 			path[i] = 1
# 		elif path[i] == b:
# 			path[i] = n
# 		elif path[i] == c:
# 			path[i] = 2
# 		elif path[i] == d:
# 			path[i] = 3
# 		elif path[i] == 1:
# 			path[i] = a
# 		elif path[i] == n:
# 			path[i] = b
# 		elif path[i] == 2:
# 			path[i] = c
# 		elif path[i] == 3:
# 			path[i] = d

n,k=list(map(int,input().split()))
a,b,s,d=input().split()
if n<5 or k<n+1: print(-1)
else:
    l=list(set(map(str,list(range(1,n+1))))-{a,b,s,d})
    print(' '.join([a,s]+l+[d,b]+[s,a]+l+[b,d]))


f = lambda: map(int, input().split())
n, k = f()
a, b, c, d = f()
s = list(set(range(1, n + 1)).difference({a, b, c, d}))
d = [a, c] + s + [d, b] + [c, a] + s + [b, d]
print(' '.join(map(str, d)) if 4 < n < k else -1)

n,k=list(map(int,input().split()))
a,b,c,d=input().split()
if n<5 or k<n+1: print(-1)
else:
    l=list(set(map(str,list(range(1,n+1))))-{a,b,c,d})
    print(' '.join([a,c]+l+[d,b]+[c,a]+l+[b,d]))


n,k=list(map(int,input().split()))

a,b,c,d=input().split()

if n<5 or k<n+1: print(-1)

else:

    l=list(set(map(str,list(range(1,n+1))))-{a,b,c,d})

    print(' '.join([a,c]+l+[d,b]+[c,a]+l+[b,d]))




# Made By Mostafa_Khaled


import sys
n, k = map(int, input().split())
a, b, c, d = map(int, input().split())
if(k<n+1 or n==4):
    print(-1)
    return
ans = [a, c]
l = [i for i in range(1, n+1) if (i!=a and i!=b and i!=c and i!=d)]
for i in l:
    ans.append(i)
ans.extend([d, b])
for i in ans:
    print(i, end=' ')
print()
ans[0], ans[1] = ans[1], ans[0]
ans[n-2], ans[n-1] = ans[n-1], ans[n-2]
for i in ans:
    print(i, end=' ')
print('\n')

n, k = list(map(int, input().split()))
a, b, c, d = list(map(int, input().split()))
if n == 4 or k < n + 1:
    print(-1)
    return
extra = 1
while extra == a or extra == b or extra == c or extra == d:
    extra += 1
v = [a, c, extra, d]
k = extra + 1
while k <= n:
    if k != a and k != b and k != c and k != d and k != extra:
        v.append(k)
    k += 1
v.append(b)
print(*v)
u = [c, a, extra] + list(reversed(v[3:]))
print(*u)