33940번 - 부분 수열 고르기 스페셜 저지

문제

길이가 $N$인 수열 $A = \{a_1, a_2, a_3, \cdots, a_N\}$는 초항이 $a$이고 공차가 $d$인 유한 등차수열이다.

양의 정수 $M$에 대하여 합이 $M$인 $A$의 부분 수열 중 가장 긴 것을 구하시오.

부분 수열이란 주어진 수열에서 원래 순서를 유지하며 0ドル$개 이상의 원소를 제거하여 얻은 수열이다.

입력

첫째 줄에 네 정수 $N,ドル $a,ドル $d,ドル $M$이 공백으로 구분되어 주어진다. $(1 \leq N, a, d \leq 10^6;$ 1ドル \leq M \leq 10^{18})$

출력

첫째 줄에 합이 $M$인 $A$의 부분 수열 중 가장 긴 것의 길이 $L$을 출력한다.

둘째 줄에 그러한 부분 수열의 원소 $L$개를 공백으로 구분하여 출력한다. 가능한 답이 여러 가지라면 그중 아무거나 출력한다.

만약 그런 부분 수열이 존재하지 않는다면 첫째 줄에 $−1$을 대신 출력한다.

제한

노트