404145: GYM101431 D Vera and Dogs

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Vera and Dogstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 Pi, 1, ..., Pi, X and the secondary home of X dogs Si, 1, ..., Si, 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

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

Output

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

Otherwise print N lines. The i-th line should contain 2X integers Pi, 1, ..., Pi, X, Si, 1, ..., Si, X. If there are multiple possible assignments, print any of them.

ExamplesInput
3 2
Output
5 1 6 4
3 6 5 2
4 2 1 3
Input
2 2
Output
-1
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.

加入题单

上一题 下一题 算法标签: