Consider a grid with rows and columns, where each cell contains a positive integer. The grid is called coprime if every cell contains an integer which is coprime with at least two of the integers written in adjacent cells. Cells are considered adjacent if they share a side, so each cell is adjacent to at most four other cells. Also, two integers are consider coprime if no integer greater than divides both of the integers.
Can you find an coprime grid that contains each integer between and (inclusive) exactly once?
To ensure the integrity of your solution, there may be up to test cases.
Subtask 1 [30%]
Subtask 2 [70%]
No additional constraints.
The first line contains a single integer .
Each of the following lines contains two space-separated integers, and .
For each test case, if no such grid exists, output
-1. Otherwise, output lines, each containing space-separated integers, representing the integers contained in the cells of the grid. If there are multiple correct solutions, any will be accepted.
2 3 3 1 3
2 3 4 1 9 7 6 5 8 -1