Yet Another Contest 7 P2 - Coprime Grid

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Consider a grid with N rows and M 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 1 divides both of the integers.

Can you find an N \times M coprime grid that contains each integer between 1 and N \times M (inclusive) exactly once?

To ensure the integrity of your solution, there may be up to T test cases.


1 \le T, N, M \le 100

Subtask 1 [30%]

N = M

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line contains a single integer T.

Each of the following T lines contains two space-separated integers, N and M.

Output Specification

For each test case, if no such grid exists, output -1. Otherwise, output N lines, each containing M space-separated integers, representing the integers contained in the cells of the grid. If there are multiple correct solutions, any will be accepted.

Sample Input

3 3
1 3

Sample Output

2 3 4
1 9 7
6 5 8


There are no comments at the moment.