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

예를 들어 바구니에 계란이 세 개, 한 개 담겨있다고 하자. 이 상태는 (3, 1, 0, 0)로 표시된다.

그러면 이 상태에서 아래와 같은 세 번의 단위 작업으로 계란을 한 바구니에 모을 수 있다.

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

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

문제는 가능한 적은 횟수의 단위 작업을 사용하여 모든 계란을 한 곳에 모으는 것이다.

여러분은 입력으로 받은 초기 바구니 상태에서 출발하여 계란이 한 바구니에 모두 담기는 최종상태까지의 중간 단계를 차례대로 출력해야 한다.

실행시간은 1초를 넘을 수 없다.

입력 형식

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

출력 형식

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

채점 기준

입력과 출력의 예

입력

4
3 1 0 0

출력

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

출처:2007 koi 중등 본선 1 번