C. Покрытие сетки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пракул усердно работал над составлением задач для Codecraft. Когда он глубоко задумывается, ему нравится прыгать по своей комнате странным, но определённым образом. Спустя некоторое время он задаётся вопросом: можно ли, прыгая таким образом, посетить все плитки в его комнате.

Комнату Пракула можно рассматривать как сетку $$$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$$$-й строке.

Поскольку Пракулу всё ещё нужно заниматься составлением задач, ему нужна ваша помощь. Определите, сможет ли он посетить все клетки в $$$A$$$ за конечное число прыжков.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит четыре целых числа $$$n, m, a, b$$$ ($$$1 \leq n, m, a, b\leq 10^{9}$$$).

Выходные данные

Для каждого набора входных данных выведите «YES», если Пракул может посетить все плитки своей комнаты, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
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$$$. Один из возможных способов посетить все клетки сетки — если Пракул начнёт с движения вниз:

  • Начать в $$$(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». Отметим, что в последних двух ходах Пракул переходит через границу сетки.

В третьем наборе входных данных: $$$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)\}$$$ навсегда остаются непосещёнными. Поскольку покрыть все клетки нельзя, ответ — «NO». Можно показать, что даже если бы Пракул начал с движения вправо в первом ходе, ответ бы не изменился.