Complex Integer Solutions

Time Limit : 8 sec, Memory Limit : 65536 KB

Problem C: Complex Integer Solutions

Let f(x) = a0 + a1x + a2x2 + ... + adxd be the function where each ai (0 ≤ id) is a constant integer (and ad is non-zero) and x is a variable. Your task is to write a program that finds all complex integer solutions of the equation f(x) = 0 for a given f(x). Here, by complex integers, we mean complex numbers whose real and imaginary parts are both integers.

Input

The input consists of two lines. The first line of the input contains d, the degree of f(x). The second line contains (d + 1) integers a0, ... , ad, the coeffcients of the equation. You may assume all the following: 1 ≤ d ≤ 10, |ai| ≤ 106 and ad ≠ 0.

Output

There should be two lines in the output. In the first line, print the number m of complex integer solutions. In the second line, print m solutions separated by space. Each solution should be counted and printed exactly once even if it is a multiple root. The solutions should be printed in ascending order of their real parts then their imaginary parts, and in the following fashion: 0, -2, i, -3i, 2+i, and 3-4i.

Sample Input 1

4
-2 0 0 0 2

Output for the Sample Input 1

4
-1 -i i 1

Sample Input 2

8
0 0 25 15 17 -10 1 -1 1

Output for the Sample Input 2

5
-1-2i -1+2i 0 2-i 2+i

Source: ACM-ICPC Japan Alumni Group Winter Camp , Day 2, Tokyo, Japan, 2009-02-22
http://acm-icpc.aitea.net/