정육면체 쌓기

다음과 같이 양의 정수를 늘어놓은 배열을 생각하자.

3 3 1
3 1
2

각 행은 왼쪽으로 정렬되어 있고, 바로 위 행보다 길지 않다. 또한 각 행을 왼쪽에서 오른쪽으로 읽으면 수가 감소하지 않고(non-increasing), 각 열을 위에서 아래로 읽어도 수가 감소하지 않는다. 이런 배열을 쌓기 패턴(stacking pattern, SP) 이라고 부른다. 이 배열은 방의 모서리에 단위 정육면체를 쌓는 방법을 나타내기 때문이다.

맨 윗 행을 한쪽 벽에, 맨 왼쪽 열을 다른 쪽 벽에 붙였다고 하자. 그러면 SP의 각 수는 그 위치에 정육면체가 몇 개 수직으로 쌓여 있는지를 위에서 내려다본 값이 된다. 위 배열은 다음과 같은 모서리 쌓기를 나타낸다.

맨 윗 행이 붙어 있는 벽을 오른쪽 벽, 맨 왼쪽 열이 붙어 있는 벽을 왼쪽 벽 이라고 부르자. 다음은 또 다른 SP와 그것이 나타내는 쌓기이다.

6 5 5 4 3 3
6 4 3 3 1
6 4 3 1 1
4 2 2 1
3 1 1
1 1 1

모서리 쌓기를 기울여서 왼쪽 벽이 바닥이 되도록(그리고 원래 바닥이 오른쪽 벽이 되도록) 하면 여전히 올바른 모서리 쌓기가 된다. 이것을 왼쪽 회전(left rotation) 이라고 부른다. 마찬가지로 오른쪽 벽이 바닥이 되도록(그리고 원래 바닥이 왼쪽 벽이 되도록) 기울이는 것을 오른쪽 회전(right rotation) 이라고 부른다.

예를 들어 첫 번째 배열의 왼쪽 회전과 오른쪽 회전은 각각 다음과 같다.

왼쪽 회전:

3 2 1
2 1 1
2 1

오른쪽 회전:

3 3 2
2 1 1
1

두 번째 배열의 왼쪽 회전과 오른쪽 회전은 모두 원래 배열과 같다는 것을 직접 확인해 볼 수 있다.

입력에는 여러 개의 문제 인스턴스가 들어 있다. 각 인스턴스는 쌓기 패턴의 행 개수를 나타내는 양의 정수 $n$ ($n \le 11$) 으로 시작한다. $n = 0$ 은 입력의 끝을 뜻한다.

이어서 패턴의 $n$ 개의 행이 한 줄에 하나씩 주어진다. 한 줄 안의 값들은 하나의 공백으로 구분되며, 줄의 끝에는 구분자 $0$ 이 붙는다. 이 $0$ 은 구분자일 뿐 패턴의 일부가 아니다. 패턴의 각 값은 $20$ 이하의 양의 정수이고, 각 행에는 값이 적어도 하나 있으며, 한 행의 값은 $20$ 개를 넘지 않는다.

각 쌓기 패턴에 대해 왼쪽 회전과 오른쪽 회전을 그 순서대로 출력한다. 각 행은 왼쪽으로 정렬하고 값들은 하나의 공백으로 구분한다. 한 패턴의 왼쪽 회전과 오른쪽 회전 사이는 빈 줄 하나로 구분하고, 서로 다른 문제 인스턴스의 출력 사이는 빈 줄 두 개로 구분한다.