← 返回题目列表

Codeforces · 2217/C

C. 网格覆盖

中文机器翻译题面 查看原题

Prakul 一直在努力为 Codecraft 设置问题。当他陷入沉思时,他喜欢以奇怪但特定的方式在房间里跳来跳去。过了一段时间,他想知道这样跳是否可以覆盖他房间的所有瓷砖。

Prakul 的房间可以被视为由 $$$n$$$ 行和 $$$m$$$ 列组成的网格 $$$A$$$。他从$$$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$$$ 行。

由于他仍然需要解决问题,因此他需要你的帮助。确定他是否可以在有限次数的跳跃中访问 $$$A$$$ 中的所有图块。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含四个整数 $$$n, m, a, b$$$ ($$$1 \leq n, m, a, b\leq 10^{9}$$$)。

输出

对于每个测试用例,打印“是“如果 Prakul 可以覆盖他房间的所有瓷砖,并且”NO”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

10
1 1 1 1
2 2 1 1
4 2 2 1
6 9 6 7
67 42 42 67
3411 4134 32 23
90234 143124 232 323
69387963 98793214 9791 4324786
985865 578977 899368 447605
1000000000 1000000000 1000000000 1000000000

输出
复制

YES
YES
NO
NO
YES
NO
NO
NO
YES
NO

注意

在第二个测试用例中:$$$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$$$ 瓷砖都被覆盖,因此答案为“是”。 请注意,Prakul 在最后两步中环绕了网格。

在第三个测试用例中:$$$n=4$$$、$$$m=2$$$、$$$a=2$$$、$$$b=1$$$。如果普拉库尔从移动开始 向下,动作如下:

  • 从 $$$(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)\}$$$ 永远不会被访问。由于并非所有瓷砖都可以覆盖,因此答案是否定的。可以证明,即使 Prakul 从移动开始 对 在第一步中,答案不会改变。