eolymp
bolt
Try our new interface for solving problems
Problems

Quadratic equation 2

Quadratic equation 2

Time limit 5 seconds
Memory limit 64 MiB

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 (1t100). Each test consists of one line containing four integers a, b, c, n, separated by a space (3n10^8, 0a, b, cn – 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
Author Evgeniy Sluzhaev