메뉴 건너뛰기

문제


시간메모리제출 회통과 회비율
1초64MB
29
1
3.4%
나의 횟수나의 판정시도 명성공 명비율
71
14.3%
문제

n개의 정수들로 이루어진 수열 \([a_1, a_2, ..., a_n]\) 이 있다. 여기에 정수 \(i\)를 주면서 '축소'라는 명령을 하면 \(a_i\) 와 \(a_{i+1}\) 이 없어지고, 대신 두 수의 차가 들어간다. 즉, 새로 들어간 수는 \(|a_i - a_{i+1}|\) 이다.

바꿔 말하면, 축소 연산 \(i\) 는

축소 \(([a_1, a_2, ... , a_n], i) = [a_1, ... , a_{i-1}, |a_i - a_{i+1}|, a_{i+2}, ... , a_n]\) 이다. 단, \(1 \leq i \leq n-1\)

예를 들어, 수열 [12, 10, 4, 3, 5]에 축소 연산들 2, 3, 2, 1을 차례대로 적용하면

축소 \(([12, 10, 4, 3, 5], 2) = [12, 6, 3, 5]\) 
축소 \(([12, 6, 3, 5], 3) = [12, 6, 2]\)
축소 \(([12, 6, 2], 2) = [12, 4]\)
축소 \(([12, 4], 1) = [8]\) 이 되므로, 마지막에 8이 남는다.

같은 수열에 축소 연산들 1, 1, 1, 1을 적용하면

축소 \(([12, 10, 4, 3, 5], 1) = [2, 4, 3, 5]\)
축소 \(([2, 4, 3, 5], 1) = [2, 3, 5]\)
축소 \(([2, 3, 5], 1) = [1, 5]\)
축소 \(([1, 5], 1) = [4]\)  가 되므로, 마지막에 4가 남는다.

입력으로 수열과 최종값이 주어질 때, \(n-1\)번의 축소 연산을 수행하여 최종값을 얻을 수 있는가를 알아내는 프로그램을 작성하시오. 최종값을 얻을 수 있는 축소 연산들이 여러 개일 경우는 그 중 하나만 출력한다.

입력

첫 줄에는 정수 \(n (1 \leq n \leq 30)\) 이 주어진다. 둘째 줄에는 최종값이 주어진다. 다음 \(n\)줄에는 \(a_1, a_2, ..., a_n\)에 해당하는 수가 한 줄에 하나씩 순서대로 주어진다. ( \(1 \leq a_i \leq 30\) )

출력

첫 줄부터 구한 축소 연산들을 한 줄에 하나씩 순서대로 출력한다. 최종값을 구할 수 없는 경우에는 첫 줄에 0을 출력한다.

예시 1
입력
5 8 12 10 4 3 5
출력
2 3 2 1
예시 2
입력
4 7 12 10 4 5
출력
0
위로