시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 6 4 36.364%

문제

네 개의 바구니에 계란이 나뉘어 담겨있다. 우리는 아래의 글상자에 제시된 단위 작업을 통하여 계란을 한 바구니에 모두 옮겨 담고자 한다. 

계란이 하나 이상 들어 있는 두 개의 서로 다른 바구니 A, B를 선택한다. 선택된 각 바구니에서 계란을 하나씩 꺼내서 A, B가 아닌 다른 바구니에 이 두 개의 계란을 담는다. 

예를 들어 바구니에 계란이 세 개, 한 개 담겨있다고 하자. 이 상태는 (3, 1, 0, 0)로 표시된다. 그러면 이 상태에서 아래와 같은 세 번의 단위 작업으로 계란을 한 바구니에 모을 수 있다. 

(3,1,0,0) → (2,0,2,0) → (1,0,1,2) → (0,0,0,4)

괄호속의 숫자는 각 바구니에 들어있는 계란의 수를 표시한 것이다. 

문제는 가능한 적은 횟수의 단위 작업을 사용하여 모든 계란을 한 곳에 모으는 것이다. 여러분은 입력으로 받은 초기 바구니 상태에서 출발하여 계란이 한 바구니에 모두 담기는 최종상태까지의 중간 단계를 차례대로 출력해야 한다. 

입력

첫째 줄에는 채점의 기준이 되는 단위 작업의 사용 횟수 K가 주어진다. 그 다음 줄에는 각 바구니에 들어있는 계란의 수가 공백을 두고 나타난다. 전체 계란의 수는 4개 이상, 3000개 이하이다. 

출력

첫 줄에는 초기 바구니의 상태를 입력형식과 동일하게 출력해야 한다. 그 다음 줄부터는 각 단계별 바구니 상태를 하나씩 출력해야 한다. 마지막 줄에는 반드시 한 바구니에 계란이 모두 모인 상태가 출력되어야 한다. 

예제 입력

4
3 1 0 0

예제 출력

3 1 0 0
2 0 2 0
1 0 1 2
0 0 0 4

힌트