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

Квадратне рівняння 2

Квадратне рівняння 2

Ліміт часу 5 секунд
Ліміт використання пам'яті 64 MiB

Задано квадратне рівняння ax^2 + bx + c ≡ 0 (mod n), де a, n – непарні натуральні числа. Гарантуєтья, що b^2-4·a·c взаємно просте з a·n. Ваша задача – розв'язати його в цілих числах.

Вхідні дані

У першому рядку вхідного файлу задано кількість тестів t (1t100). Кожен тест складається з одного рядка, який містить чотири цілих числа a, b, c, n, відокремлених одним пропуском (3n10^8, 0a, b, cn – 1).

Вихідні дані

Для кожного тесту виведіть рядок, який містить усі корені рівняння з діапазону [0, n-1]. Корені необхідно вивести через пропуск у порядку зростання (зверніть увагу, що у кінці рядка пропуск не потрібний). Якщо для поточного тесту коренів немає виведіть "NO SOLUTION" без лапок.

Приклад

Вхідні дані #1
3
1 0 2 3
1 1 0 3
3 4 0 5
Вихідні дані #1
1 2
0 2
0 2
Автор Євген Служаєв