CF2217C Grid Covering

Prakul 一直在为 Codecraft 设计算法题而努力工作。当他陷入沉思时，他喜欢以奇怪但特定的方式在房间里跳来跳去。一段时间后，他想知道，这样的跳跃方式能否覆盖他房间里的所有瓷砖。 Prakul 的房间可以被视作一个 $A$ 矩阵，共有 $n$ 行 $m$ 列。他从 $A_{1,1}$ 开始。如果他现在在 $A_{i,j}$，他可以选择以下两种方式中的一种跳跃： - 向右跳 $b$ 步到 $A_{i,\;((j+b-1)\bmod m)+1}$； - 向下跳 $a$ 步到 $A_{((i+a-1)\bmod n)+1,\;j}$。 有一个特殊的限制条件：他可以用任意一种方式作为第一步，但之后必须交替进行两种跳跃。 注意，他的房间非常特殊，是环绕的。在第 $m$ 列再向右走一步，会到第 $1$ 列。同理，在第 $n$ 行再向下走一步，会到第 $1$ 行。 由于 Prakul 还要继续出题，他需要你的帮助。请你判断他是否能在有限步内覆盖房间中的所有瓷砖。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例只包含一行，包含四个整数 $n, m, a, b$（$1 \leq n, m, a, b\leq 10^{9}$）。

对于每个测试用例，如果 Prakul 能覆盖房间内的所有瓷砖，输出 "YES"。否则输出 "NO"。 你可以使用任意大小写输出答案。例如，"yEs", "yes", "Yes", "YES" 都会被认为是肯定的回答。

在第二个测试用例中：$n=2$，$m=2$，$a=1$，$b=1$。Prakul 如果开始选择向下移动： - 从 $(1, 1)$ 开始。 - 向下跳 $a=1$ 步：$(1, 1) \to (2, 1)$。 - 向右跳 $b=1$ 步：$(2, 1) \to (2, 2)$。 - 向下跳 $a=1$ 步：$(2, 2) \to (1, 2)$。 - 向右跳 $b=1$ 步：$(1, 2) \to (1, 1)$。 访问的瓷砖序列为 $\{(1,1), (2,1), (2,2), (1,2) \}$。在这种情况下，总共 $2 \cdot 2 = 4$ 块瓷砖全部被覆盖，因此答案为 "YES"。注意最后两步 Prakul 会环绕到格子起始处。 在第三个测试用例中：$n=4$，$m=2$，$a=2$，$b=1$。如果 Prakul 开始选择向下移动，跳跃过程如下： - 从 $(1, 1)$ 开始。 - 向下跳 $a=2$ 步：$(1, 1) \to (3, 1)$。 - 向右跳 $b=1$ 步：$(3, 1) \to (3, 2)$。 - 向下跳 $a=2$ 步：$(3, 2) \to (1, 2)$。 - 向右跳 $b=1$ 步：$(1, 2) \to (1, 1)$。 - $\cdots$ 这种情况下，瓷砖 $\{(2, 1),(2, 2),(4, 1), (4, 2)\}$ 永远不会被访问到。由于不是所有的瓷砖都能被覆盖，答案为 "NO"。可以证明，即使 Prakul 第一跳选择向右，结论也不会改变。 由 ChatGPT 5 翻译