최대공약수

면접 대비

시간 제한2초메모리 제한512 MB

요약

n개의 수 중에서 최대공약수가 정확히 d가 되는 부분집합을 고르고, 그런 부분집합이 없으면 -1을 출력합니다.

난이도: 쉬움10점 중 3점
유형: 정수론, 구현
정답자: 아직 제출이 없습니다

문제

페티야는 종이에 $n$ 개의 수 $a_1, \ldots, a_n$ 을 적었다. 이 수들은 친구들이 사는 집의 번호이다. 페티야는 이 수들 중에서 최대공약수가 자신이 좋아하는 수 $d$ 와 같아지도록 부분집합을 고르고 싶어 한다. 페티야가 부분집합을 고르도록 도와주세요.

입력

첫 줄에 정수 $n$ 과 $d$ 가 주어진다 ( $1 \le n \le 1000$ , $1 \le d \le 10^9$ ). 둘째 줄에는 정수 $a_1, \ldots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^9$ ).

출력

조건을 만족하는 부분집합이 존재하면 첫 줄에 부분집합의 원소 개수 $k$ 를 출력한다. 둘째 줄에는 부분집합에 속한 수를 출력한다. 부분집합이 존재하지 않으면 첫 줄에 $-1$ 을 출력한다. 답이 여러 개면 그중 아무거나 출력해도 된다.

예제2

예제 1
입력
```
4 3
6 8 12 9
```
예상 출력
```
2
6 9
```
예제 2
입력
```
3 3
2 4 8
```
예상 출력
```
-1
```