무게 오버플로

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

요약

n개의 추와 모듈러 m이 주어질 때, 무게의 합을 m으로 나눈 나머지가 같은 서로 겹치지 않는 두 부분집합을 찾고, 없으면 -1을 출력합니다.

난이도: 보통10점 중 7점
유형: 완전 탐색, 해시맵, 정수론
정답자: 아직 제출이 없습니다

문제

존은 최근 유명한 웹사이트에서 전자 저울을 샀다. 이 저울에는 물건을 올릴 수 있는 접시가 두 개 있다. 물건을 올리면 저울은 어느 접시가 다른 접시보다 무거운지, 또는 두 접시의 무게가 같아서 균형이 맞는지 알려 준다.

존은 저울을 실험하다가 결과가 가끔 이상하다는 것을 알아냈다. 저울은 각 접시에 올라간 물건의 무게를 그램 단위로 모두 더한 뒤 두 값을 비교한다. 그런데 이 소프트웨어는 예전 스포츠 프로그래머들이 작성했기 때문에, 저울은 각 접시의 무게를 어떤 정수 $m$ 로 나눈 나머지로 계산한다.

존에게는 특수 추가 $n$ 개 있다. $i$ 번째 추의 질량은 $a_i$ 그램이다. 존은 이 추 일부를 접시에 올려서 저울이 균형을 이루게 하려고 한다. 추는 적어도 하나는 올려야 한다.

입력

첫째 줄에 존이 가진 추의 개수 $n$ 과 무게 계산에 쓰는 나머지 연산의 법 $m$ 이 정수 두 개로 주어진다 ( $1 \le n \le 25$ ; $1 \le m < 4 \cdot 10^7$ ).

둘째 줄에는 추의 질량 $a_1, \ldots, a_n$ 이 정수 $n$ 개로 주어진다 ( $1 \le a_i \le 10^9$ ).

출력

답이 있으면 첫째 줄에 첫 번째 접시에 올릴 추의 개수 $k$ 를 출력한다. 둘째 줄에는 그 추들의 번호를 출력한다.

이어서 두 번째 접시에 올릴 추의 개수 $l$ 을 다음 줄에 출력한다. 그다음 줄에는 그 추들의 번호를 출력한다.

추의 번호는 입력 순서대로 1부터 $n$ 까지 매긴다.

답이 없으면 "-1"이라는 숫자 하나만 출력한다.

예제2

예제 1
입력
```
4 14
1 3 7 10
```
예상 출력
```
1
4
2
2 3
```
예제 2
입력
```
3 7
1 2 4
```
예상 출력
```
3
1 2 3
0
```