Hints: Grid Covering

Read $n$, $m$, $a$, and $b$ for each test case.

If $\gcd(n, a) > 1$, print NO and stop: the model rejects this case immediately.

If $\gcd(m, b) > 1$, print NO and stop.

If $\gcd(n, m) > 2$, print NO and stop.

Otherwise print YES.

Because moves must alternate, group them in pairs.

If you start with down, every 2 moves do:

$$ (i, j) \mapsto (i + a, j + b) \pmod{(n,m)}. $$

So a single arithmetic progression on the torus appears.

Answer to Hint 1:
Let

$$ S_0 = \{(ta \bmod n,\; tb \bmod m)\}, $$

for integer $t \ge 0$ (ignoring +1 index shift).

These are positions after each full 2-move block. What about odd steps?

Answer to Hint 2:
For down-first:

• even steps give $S_0$,
• odd steps give $S_1 = \{((t+1)a \bmod n,\; tb \bmod m)\}$.

So visited cells are contained in $S_0 \cup S_1$.

Answer to Hint 3:
Let $L$ be the period (order) of vector $(a,b)$ in $\mathbb{Z}_n \times \mathbb{Z}_m$:

$$ L = \operatorname{lcm}\!\left(\frac{n}{\gcd(n,a)},\; \frac{m}{\gcd(m,b)}\right). $$

Then $|S_0| = L$, and also $|S_1| = L$, so at most $2L$ cells can be visited.

Answer to Hint 4:
To visit all $n \cdot m$ cells, we need $n m \le 2L$.

A stronger necessary condition comes first: all row residues and all column residues must be reachable.

That forces:

$$ \gcd(n,a)=1,\quad \gcd(m,b)=1. $$

Answer to Hint 5:
Under $\gcd(n,a)=\gcd(m,b)=1$:

$$ L = \operatorname{lcm}(n,m) = \frac{nm}{\gcd(n,m)}. $$

So

$$ nm \le 2L \iff \gcd(n,m) \le 2. $$

Hence $\gcd(n,m)\le 2$ is also necessary.

Answer to Hint 6:
Now show sufficiency:

• If $\gcd(n,m)=1$, then $L=nm$, so $S_0$ alone already has all cells.
• If $\gcd(n,m)=2$, then $L=nm/2$. In this case $S_0$ and $S_1$ are disjoint, so together they have $nm$ cells.

So all cells are covered.

Final test per case is exactly:

$$ \gcd(n,a)=1,\quad \gcd(m,b)=1,\quad \gcd(n,m)\le 2. $$

If all hold print YES, else NO. Complexity is $O(\log \max(n,m,a,b))$ from gcd computations.