Quadratic Equations

Problem code: E4

All submissions for this problem are available.

A tutorial for this problem is available here.

Knowing Johnny's mathematical talent, our teacher has prepared a new interesting problem for him, hoping he will enjoy solving it. The problem description is given below.

"There is a rectangular room of length l and width w (l and w are integers). The length and width of the room  fulfill the relation l=Aw+B, where A and B are given integer constants. The room is divided into square cells of unit dimensions. You have observed that, after adding an integer C to the number of cells in the room, the number of cells becomes divisible by the prime number P. Find all the possible values of the width of the room."

 

Input

The first line contains t, the number of test cases (about 10000). Then t test cases follow. Each test case is given in one line containing 4 integers A, B, C and P (2 ≤ P < 106, 0 < A < P, 0 ≤ B,C < P).

P is always a prime number.

Output

For each test case, write the result in one line. The first number K is the number of solutions. Then K numbers X1, X2, ...,XK follow (0 ≤ Xi < P), which are the solutions to the corresponding problems.

Example

Input:
2
1 1 0 2
1 2 2 3

Output:
2 0 1
0

Date: 2009-06-05
Time limit: 1

s
Source limit: 50000
Languages: C C99 strict C++ PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp HASK CAML CLPS PRLG WSPC BF ICK TEXT


Comments

kyun @ 1 Jul 2009 09:29 PM

Are trailing spaces at the end of the solution lines a problem?

kyun @ 1 Jul 2009 09:39 PM

Please ignore my post. Got it very wrong.

caa0502 @ 2 Jul 2009 04:10 AM

Solution for test case 1 seems incomplete. Can anyone please clarify? I see that it can take more than 2 values based on the divisibility criteria. Please correct me if I am wrong. Admins, can you provide more test cases, please?

aupadhyay @ 2 Jul 2009 04:18 AM

@sriram, solution is correct. note that 0<= xi < P. So your divisors must be less than P.

i0exception @ 2 Jul 2009 05:19 PM

@Sriram Your answers should be numbers less than P

ashokb @ 3 Jul 2009 04:17 AM

what does "Time limit of 3s" mean? Should the program complete the execution of all the test cases (about 10000) in max. 3secs?

sush @ 3 Jul 2009 04:33 AM

i guess so :(

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions