문제
피터는 분자(molecule)를 판별하는 기계를 만드는 회사에서 일한다.
각 분자의 무게는 양의 정수이다.
이 기계에는 판별 범위 [l, u]라는 것이 있다(단, l과 u는 양의 정수).
기계가 분자들의 집합을 판별할 수 있는 경우는, 이 집합이 다음과 같은 부분집합을 갖는 경우와 같다: 부분집합에 속하는 분자들의 총 무게가 이 기계의 판별 범위에 속한다.
다시 말해서, n개의 분자가 주어지고 이 분자들의 무게는 w0, ..., wn-1이라고 가정하자.
이때 l ≤ wi1 + ... + wim ≤ u 를 만족하는 서로 다른 인덱스들의 집합 I = {i1, ..., im} 가 존재한다면 판별은 성공이다.
기계의 명세에 따르면, l과 u의 차이는 가장 무거운 분자와 가장 가벼운 분자의 무게 차이보다 크거나 같다는 것이 보장된다.
즉, wmax = max(w0, ..., wn-1) 와 wmin = min(w0, ..., wn-1) 에 대해 u - l ≥ wmax - wmin 이다.
여러분은 판별 범위에 속하는 총 무게를 갖는 임의의 부분집합을 찾거나 또는 그런 부분집합이 없음을 판단하는 프로그램을 작성하면 된다.
입력
1번 줄 : n, l, u
2번 줄 : w0, ..., wn-1
1 ≤ n ≤ 200000, 1 ≤ wi, l, u < 231
출력
만약 요구되는 부분집합이 존재한다면, 그런 부분집합 중 임의의 하나에 대한 분자들의 인덱스들의 집합 I = {i1, ..., im}에 대하여 첫 번째 줄에 m, 두 번째 줄에 i1, ..., im을 공백으로 구분하여 출력한다.
만약 요구되는 부분집합이 존재하지 않는다면 첫 번째 줄에 0을 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 점 | 1 ≤ n ≤ 100, 1 ≤ wi ≤ 100, 1 ≤ u, l ≤ 1 000, 모든 wi는 동일 |
| #2 | 점 | 1 ≤ n ≤ 100, 1 ≤ wi, u, l ≤ 1 000, max(w0, w1, ... , wn-1) - min(w0, w1, ... , wn-1) ≤ 1 |
| #3 | 점 | 1 ≤ n ≤ 100, 1 ≤ wi, u, l ≤ 1 000 |
| #4 | 점 | 1 ≤ n ≤ 10 000, 1 ≤ wi, u, l ≤ 10 000 |
| #5 | 점 | 1 ≤ n ≤ 10 000, 1 ≤ wi, u, l ≤ 500 000 |
| #6 | 점 | 문제의 조건 외에 주어진 제한이 없다. |
예제1
41517
6887
2
13