EduBrick

E. Система линейных сравнений

1000 мс · 256 МБ · всё или ничего

Дана система из двух сравнений

{x≡a(modn)x≡b(modm)\begin{cases} x \equiv a \pmod n \\ x \equiv b \pmod m \end{cases}

где nn и mm не обязательно взаимно просты. Решите её или определите, что решений нет.

Формат ввода

В первой строке - число систем tt (1≤t≤1051 \le t \le 10^5).

В следующих tt строках - по четыре числа aa, bb, nn, mm. Все числа по модулю не превосходят 10410^4, при этом n>1n > 1, m>1m > 1.

Формат вывода

Для каждой системы выведите строку.

Если решений нет — NO. Иначе — YES и два числа x0x_0 и pp (0≤x0<p0 \le x_0 < p), задающих множество решений x=x0+kpx = x_0 + kp.

Примеры

ввод
3
3 2 5 9
1 1 5 9
7 13 20 24
вывод
YES 38 45
YES 1 45
NO
ввод
1
1 0 2 4
вывод
NO
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.