Problems
Quadratic equation 2
Quadratic equation 2
Given the quadratic equation ax^2 + bx + c ≡ 0 (mod n), where a, n – an odd natural numbers. It is guaranteed that the b^2-4·a·c is prime to a·n. Your task is to solve it in integers.
Input data
The first line of the input file contains the number of tests t (1 ≤ t ≤ 100). Each test consists of one line containing four integers a, b, c, n, separated by a space (3 ≤ n ≤ 10^8, 0 ≤ a, b, c ≤ n – 1).
Output data
For each test case output a string containing all the roots of the range [0, n-1]. The roots need to give a space in ascending order (note that in the end of the line space is not needed). If the current test, the roots do not output "NO SOLUTION" without the quotes.
Examples
Input example #1
3 1 0 2 3 1 1 0 3 3 4 0 5
Output example #1
1 2 0 2 0 2