Greatest Common Divisor

Interview

Time limit2sMemory limit512 MB

Summary

Given n numbers, choose a subset whose greatest common divisor is exactly d, or report -1 if no such subset exists.

Level: Easy3 of 10
Topics: Number theory, Implementation
Solved: No attempts yet

Statement

Petya wrote $n$ numbers $a_1, \ldots, a_n$ on a sheet of paper. They are the house numbers where his friends live. He wants to choose a subset of these numbers whose greatest common divisor is equal to his favorite number $d$ . Help Petya choose the subset.

Input

The first line contains two integers $n$ and $d$ ( $1 \le n \le 1000$ , $1 \le d \le 10^9$ ). The second line contains $n$ integers $a_1, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ).

Output

If a suitable subset exists, print its size $k$ on the first line. Print the numbers in the subset on the second line. If no solution exists, print $-1$ on the first line. If there are several answers, print any of them.

Examples2

Example 1
Input
```
4 3
6 8 12 9
```
Expected output
```
2
6 9
```
Example 2
Input
```
3 3
2 4 8
```
Expected output
```
-1
```