Description

Never gonna give you up~

Never gonna let you down~

Never gonna run around and desert you~

~ by Rick Astley

Rick will never let you down, but today he will let you count.

He's no stranger to count.

You know the rules and so you code.

A full commitment of coding is what you are thinking of.

You wouldn't get this from any other guy.

You just wanna tell Rick how you're coding.

Gotta make Rick understand.

(video support)

 

You got n numbers a_i( 1 ≤ i ≤ n) and a number k denotes a number system with base k.

You are ask to figure out how many different last digit can be found by the

sum of several a_i (Σa_iw_i for w_i∈{N,0},1≤i≤n) (p.s. N means natural number )

in the number system with base k.

Output how many number of digits you can found and output all the digits in increasing order.

Example

If you got n = 2 and k = 8 .

{ a_i | 1 ≤ i ≤ 2 }= { 12, 20 }

12 can be written as 14 in the number system with base 8, thus we found 4.

20 can be written as 24 in the number system with base 8 , thus we found 4.

20 + 12 = 32 can be written as 40 in the number system with base 8 , thus we found 0.

20 + 20 + 12 = 52 can be written as 64 in the number system with base 8 , thus we found 4.

........

After trying all possible number of 20w₁ + 12w₂ (w_1, w₂  ∈{N,0} ) we found that

we can only found {0, 4}.

You then need to output the answer:

2

0 4

 

Hint

If you try to brute force list all the possible number of linear combination of a_i you won't solve this problem!

Input

The input will end by EOF.

There will be multiple queries in one testcase but for each testcase there won't exceed 10 queries.

For each queries, there are two lines.

First line contains two integer n, k (1 ≤ n ≤ 10⁵, 2 ≤ k ≤ 10⁵).

Second line contains n integer a_i ( 1 ≤ a_i ≤ 10⁹ ).

 

Output

For each queries the output contains two lines.

The first line contains the number of different last digit can be found.

The second line contains the different last digit you found.

Seperate each number by one blank, note that there's no blank follow the last number.

Remember to print \n at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss