3198 - 디코딩

• Submit
• Status
• Discuss
• Summary

Description

지아희조와 이노인호는 서로 사랑하는 사이이다. 하지만 사회의 눈초리는 그들의 관계를 인정해주지 않았고, 때문에 둘은 비밀연애를 하게 되었다.

지아희조와 이노인호는 서로의 대화내용이 들키지 않게 만들기 위해, 둘만의 비밀암호를 하나 만들었다.

 

그들은 먼저 행렬의 세로(R)와 가로(C)를 비밀스럽게 정했다. 보내는 사람은 다음과 같은 법칙을 이용하여 문자열의 중간형태를 인코딩한다.

문자는 대문자와 『　　』(공백) 으로 이루어진다. 각 문자들은 아래와 같은 10진수로 대응된다.

 

『　　』 = 0, A = 1, B = 2, C = 3, ... , Y = 25, Z = 26

보내는 사람은 보내려는 문자의 10진수 값을 5자리 이진수로 변환하여 행렬을 만든다. 행렬을 만드는 순서는 아래의 그림에서 표시된 순서를 따른다.

 

 

0		0		0		0
						↓
1		1		0		1
↑				↓		↓
0		0		1		0
↑						↓
1		1		0		0

 

 

A = 00001, C = 00011, M = 01101

(one extra 0)

위의 예시는 R=4, C=4 일 때 ACM 이라는 문자열을 행렬로 만들었을 때의 모습이다. 남는 공간에는 0을 채운다.

 

이렇게 만들어진 행렬에서 제일 위쪽 행부터 시작해서 행들의 값을 한줄로 합쳐서 상대편에게 보낸다. 위의 예시에서는 0000110100101100 으로 인코딩 된다.

 

 

이노인호는 지금까지 받은 사랑의 메세지들을 정리하기로 결정했다. 그러나  메세지들은 모두 인코딩된 상태로 저장되어져 있었기 때문에 일일히 해독하는데 많은 시간이 필요했다. 그래서 아두인호는 비밀 메세지를 대신 해독해주는 프로그램을 당신에게 부탁했다.

남자가 봐도 반하겠는 이노인호의 매력에 빠진 당신은 이제 이 프로그램을 만들어주어야한다. 화이팅!

 

Input

첫 줄에는 테스트케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다.

각 테스트케이스마다 R C, 그리고 인코딩된 문자열 C가 한줄에 걸쳐 주어진다. (1≤R,C≤20)

Output

각각 테스트케이스마다 한줄에 하나씩 다음의 형식에 맞춰서 출력한다.

i P

i는 테스트케이스의 번호이고, P는 C를 해독한 결과물이다.

P의 결과 문자에서 앞뒤로 불필요한 공백이나 조각난 문자가 들어오는 경우 이를 무시한 결과를 출력한다.

Sample Input

4
4 4 0000110100101100
5 2 0110000010
2 6 010000001001
5 5 0100001000011010110000010

Sample Output

1 ACM
2 HI
3 HI
4 HI HO

Source

Regionals 2007, North America - Greater NY