슈퍼 2048

2048은 격자 위의 타일을 밀어 서로 합치고 숫자 2048가 적힌 타일을 만드는 것이 목표인 유명한 일인용 게임이다.

2048은 플레이어가 움직이면 타일이 부드럽게 미끄러지는 단순한 4 x 4 격자에서 진행된다. 각 이동에서 플레이어는 모든 타일을 4개 방향인 왼쪽, 오른쪽, 위쪽, 아래쪽 중 하나로 동시에 가능한 한 멀리 이동시킬 수 있다. 같은 숫자의 타일 두 개가 이동 중 충돌하면, 충돌한 두 타일의 값을 합한 값을 가진 타일 하나로 합쳐진다. 한 번의 이동에서 새로 만들어진 타일은 다시 합쳐질 수 없으며, 항상 이동 방향을 따라 바로 옆에 있는 타일과 먼저 합쳐진다. 예를 들어 "2" 세 개가 "2 2 2"과 같이 한 행에 있고 플레이어가 왼쪽으로 이동하기로 선택하면 "4 2 0"가 되며, 가장 왼쪽의 2 "2"가 합쳐진다.

위 그림은 플레이어가 모든 타일을 '오른쪽'으로 이동시킬 때 4 x 4 격자가 어떻게 변하는지 보여 준다.

Alice와 Bob은 우연히 이 게임을 발견하고 두 타일이 합쳐질 때의 느낌을 좋아하게 된다. 몇 판을 진행한 뒤 보드 크기에 싫증이 난 그들은 보드 크기를 N x N으로 확장하기로 하고, 이 게임을 "Super 2048"이라고 불렀다.

커진 보드에 그들은 이내 현기증을 느낀다(괜히 일을 벌여 고생한다 -_-| ). 그들은 주어진 보드의 모든 타일을 특정한 한 방향으로 이동시킨 뒤 보드가 어떤 모습일지 알아내도록 도와주는 프로그램을 작성해 달라고 요청한다.

제한

테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 격자의 각 수는 0이거나, 2 이상 1024 이하인 이의 거듭제곱이다.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 20 1 ≤ N ≤ 4

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 100 1 ≤ N ≤ 20

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 보드의 한 변의 길이 N과 타일이 이동할 방향 DIR가 주어진다. N과 DIR는 하나의 공백으로 구분된다. DIR는 "left", "right", "up", "down"의 네 문자열 중 하나이다.

다음 N개의 줄에는 각각 보드의 초기 상태를 설명하는, 공백으로 구분된 N개의 정수가 주어진다. 각 줄은 위에서 아래 순서로 보드의 한 행을 나타내며, 각 정수는 타일의 값을 나타낸다(또는 해당 위치에 숫자가 없으면 0을 나타낸다).

각 테스트 케이스마다 "Case #x:"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이다. 그런 다음 각각 이동 후의 보드를 입력과 같은 형식으로 설명하는, 공백으로 구분된 N개의 정수를 포함하는 N개의 줄을 더 출력한다.