eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Квадратное уравнение 1

Квадратное уравнение 1

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Задано квадратное уравнение ax^2 + bx + c ≡ 0 (mod p), где a > 0 и p – нечетное простое число.

Ваша задача выяснить, имеет ли оно решение в целых числах.

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

В первой строке входного файла задано количество тестов t (1t100000). Каждый тест состоит из одной строки, содержащей четыре целых числа a, b, c, p, разделенных одним пробелом (3p2·10^9, 0 < ap–1, 0b, cp–1). Гарантируется, что входные данные удовлетворяют описанным в условии задачи ограничениям.

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

Для каждого теста выведите строку, содержащую "YES" если уравнение имеет решение, и "NO" в противном случае.

Пример

Входные данные #1
3
1 2 1 7
1 3 1 7
1 3 1 11
Выходные данные #1
YES
NO
YES
Автор Евгений Служаев