Vera and Dogs

Vera owns N doghouses numbered from 1 to N and M = X · N dogs numbered from 1 to M. Each doghouse should be the primary home of X dogs P_i,1, …, P_i,X and the secondary home of X dogs S_i,1, …, S_i,X. Each dog should have one primary home and one secondary home different from its primary home. Every night, at most one doghouse might be unavailable due to cleaning. Each dog will sleep in its primary home if it is available, otherwise it will sleep in its secondary home. Each doghouse should contain at most X + 1 sleeping dogs on any night.

Help Vera find a valid assignment of doghouses to dogs or determine that it is impossible.

Input Specification

Line 1 contains integers N and X (1 ≤ N, X ≤ 2017, X · N ≤ 50 000).

Output Specification

If it is impossible to find a valid assignment, print one line with –1.

Otherwise print N lines. The ith line should contain 2X integers P_i,1, …, P_i,X, S_i,1, …, S_i,X. If there are multiple possible assignments, print any of them.

Sample Input 1

1. 3 2

download as text file

Output for Sample Input 1

1. 5 1 6 4
2. 3 6 5 2
3. 4 2 1 3

download as text file

Sample Input 2

1. 2 2

download as text file

Output for Sample Input 2

1. -1

download as text file

Note

For the first example:

Doghouse 1 is the primary home of dogs 5 and 1 and secondary home of dogs 6 and 4. If doghouse 1 is unavailable, then dog 1 will sleep in doghouse 3 and dog 5 will sleep in doghouse 2.

Doghouse 2 is the primary home of dogs 3 and 6 and secondary home of dogs 5 and 2. If doghouse 2 is unavailable, then dog 3 will sleep in doghouse 3 and dog 6 will sleep in doghouse 1.

Doghouse 3 is the primary home of dogs 4 and 2 and secondary home of dogs 1 and 3. If doghouse 3 is unavailable, then dog 4 will sleep in doghouse 1 and dog 2 will sleep in doghouse 2.

So it can be seen that no doghouse will ever contain more than 3 dogs.