Note that there are many possible constructions which are not illustrated in this editorial.

Subtask 1

Observe that every integer $X$ is coprime with both $X-1$ and $X+1$. It would therefore be useful to have consecutive integers in adjacent cells. This motivates a 'snake' pattern, where an example is shown for $N=M=5$:

 1  2  3  4  5
10  9  8  7  6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

This grid is coprime because:

• $1$ is coprime with all integers, and so is coprime with the two integers adjacent to it.
• $X$ is adjacent to $X-1$ and $X+1$, for all $1<X<N^2$.
• $N^2$ is adjacent to $N^2-1$ and $(N-1{)}^2$, which are both coprime with it. Note that $N-1$ and $N$ do not share any prime factors, so $(N-1{)}^2$ and $N^2$ must also have no prime factors in common.

Time complexity: $\mathcal{O}(NM)$

Subtask 2

Our construction from subtask 1 does not always work because $NM$ is not always coprime with $NM-2M+1$. It's possible that $NM$ is coprime with neither $NM-2M+1$ nor $NM-2N+1$, so snaking vertically rather than horizontally does not work either. Instead, we can make a simple modification to our snake: we snake from $2$ to $NM$, and place $1$ in the remaining cell. For example, when $N=5$ and $M=6$, our construction looks like:

 2  3  4  5  6  7
13 12 11 10  9  8
14 15 16 17 18 19
25 24 23 22 21 20
26 27 28 29 30  1

This grid is coprime because:

• $1$ is coprime with all integers, and so is coprime with the two integers adjacent to it.
• $2$ is adjacent to $3$ and $2M+1$, both of which are odd.
• $X$ is adjacent to $X-1$ and $X+1$, for all $2<X<NM$.
• $NM$ is adjacent to $NM-1$ and $1$, which are both coprime with it.

There is an alternate construction where we change the path that the snake takes, such that $NM$ ends up next to either $1$ or $2$. Any such grid would be coprime because:

• $1$ is coprime with all integers, and so is coprime with the two integers adjacent to it.
• $X$ is adjacent to $X-1$ and $X+1$, for all $1<X<NM$.
• $NM$ is adjacent to $NM-1$, and either $1$ or $2$, which are both coprime with it. We can show that if $NM$ is next to $2$, it is coprime with it; if we checkerboard the grid, alternating black and white cells, we see that integers of the same parity are in the same colour of cell. Since $NM$ and $2$ would be in different coloured cells, they must have opposite parities, so $NM$ is odd and therefore coprime with $2$.

Time complexity: $\mathcal{O}(NM)$