시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 58 25 20 41.667%

문제

규현이는 승환이에게 사랑을 담은 문자 메시지를 자주 보낸다. 이것을 남에게 보이기 싫었던 규현이는 승환이와 비밀 규칙을 만들었다.

규현이는 비밀 메시지를 만들기 위한 행렬의 행의 수 R과 열의 수 C를 정했다. 그 다음 다음과 같은 규칙으로 비밀 메시지를 만든다.

  1. 모든 글자는 알파벳 대문자와 공백으로 이루어져 있다.
  2. 글자는 다음과 같이 숫자로 바뀐다. 공백 = 0, A = 1, B = 2, ..., Y = 25, Z = 26

먼저 규현이는 문자를 위 규칙을 이용해 글자를 숫자로 바꾼 다음에 이것은 5자리 이진수로 바꾼다. 그 다음 아래 그림과 같이 소용돌이 패턴으로 행렬에 채운다. 행렬의 모든 칸을 채우지 못할 때는, 0으로 계속 채운다. 예를 들어 규현이가 보내려는 메시지가 "ACM"이고, R=4, C=4로 정했다면, 다음과 같이 행렬을 채우면 된다.

A = 00001, C = 00011, M = 01101, 모자라는 칸은 0으로 채운다.

그 다음 행렬을 행 우선으로 읽은 뒤 (Row Major Order)에 승환이에게 보낸다.

위의 예시를 메시지로 보낸다면 0000110100101100이 된다.

승환이가 받은 비밀 메시지와 R과 C가 주어졌을 때, 이를 규현이가 보낸 문자 메시지로 변환하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 <= T <= 1,000) 각 테스트 케이스는 한 줄로 이루어져 있고, R, 공백, C, 공백, 승환이가 받은 메시지로 이루어져 있다. (1<=R,C<=20) 메시지는 0과 1로만 이루어져 있고, 이 길이는 항상 R*C이다.

출력

각 테스트 케이스에 대해 규현이가 보내려고 변환되기 전 문자 메시지를 출력한다. 이 때, 원래 문자 메시지가 공백으로 끝난다면, 그 공백을 모두 제거한 뒤에 출력한다.

예제 입력 1

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

예제 출력 1

ACM 
HI 
HI 
HI HO
W3sicHJvYmxlbV9pZCI6IjI3MTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzhcdWM3OTBcdWI5N2MgXHViYzFiXHVjNzQwIFx1YzJiOVx1ZDY1OFx1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZGRjXHVkNjA0XHVjNzc0XHViMjk0IFx1YzJiOVx1ZDY1OFx1Yzc3NFx1YzVkMFx1YWM4YyBcdWMwYWNcdWI3OTFcdWM3NDQgXHViMmY0XHVjNzQwIFx1YmIzOFx1Yzc5MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVjNzkwXHVjOGZjIFx1YmNmNFx1YjBiOFx1YjJlNC4gXHVjNzc0XHVhYzgzXHVjNzQ0IFx1YjBhOFx1YzVkMFx1YWM4YyBcdWJjZjRcdWM3NzRcdWFlMzAgXHVjMmViXHVjNWM4XHViMzU4IFx1YWRkY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWMyYjlcdWQ2NThcdWM3NzRcdWM2NDAgXHViZTQ0XHViYzAwIFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRkY1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWJlNDRcdWJjMDAgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVkNTg5XHViODJjXHVjNzU4IFx1ZDU4OVx1Yzc1OCBcdWMyMTggUlx1YWNmYyBcdWM1ZjRcdWM3NTggXHVjMjE4IENcdWI5N2MgXHVjODE1XHVkNTg4XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGRjXHVjZTU5XHVjNzNjXHViODVjIFx1YmU0NFx1YmMwMCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHViOWNjXHViNGUwXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YmFhOFx1YjRlMCBcdWFlMDBcdWM3OTBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1YzY0MCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhZTAwXHVjNzkwXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjMjJiXHVjNzkwXHViODVjIFx1YmMxNFx1YjAxMFx1YjJlNC4mbmJzcDtcdWFjZjVcdWJjMzEgPSAwLCBBID0gMSwgQiA9IDIsIC4uLiwgWSA9IDI1LCBaID0gMjY8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAgXHVhZGRjXHVkNjA0XHVjNzc0XHViMjk0IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM3MDQgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMjJiXHVjNzkwXHViODVjIFx1YmMxNFx1YWZiYyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjNzc0XHVhYzgzXHVjNzQwIDVcdWM3OTBcdWI5YWMgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YmMxNFx1YWZiY1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWMxOGNcdWM2YTlcdWIzY2NcdWM3NzQgXHVkMzI4XHVkMTM0XHVjNzNjXHViODVjIFx1ZDU4OVx1YjgyY1x1YzVkMCBcdWNjNDRcdWM2YjRcdWIyZTQuIFx1ZDU4OVx1YjgyY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YzljMCBcdWJhYmJcdWQ1NjAgXHViNTRjXHViMjk0LCAwXHVjNzNjXHViODVjIFx1YWNjNFx1YzE4ZCBcdWNjNDRcdWM2YjRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVhZGRjXHVkNjA0XHVjNzc0XHVhYzAwIFx1YmNmNFx1YjBiNFx1YjgyNFx1YjI5NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWFjMDAgJnF1b3Q7QUNNJnF1b3Q7XHVjNzc0XHVhY2UwLCBSPTQsIEM9NFx1Yjg1YyBcdWM4MTVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVkNTg5XHViODJjXHVjNzQ0IFx1Y2M0NFx1YzZiMFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMDYlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDEyXzM2XzM1LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NXB4OyB3aWR0aDoxMjZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BID0gMDAwMDEsIEMgPSAwMDAxMSwgTSA9IDAxMTAxLCBcdWJhYThcdWM3OTBcdWI3N2NcdWIyOTQgXHVjZTc4XHVjNzQwIDBcdWM3M2NcdWI4NWMgXHVjYzQ0XHVjNmI0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHViMmU0XHVjNzRjIFx1ZDU4OVx1YjgyY1x1Yzc0NCBcdWQ1ODkgXHVjNmIwXHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3ZFx1Yzc0MCBcdWI0YTQgKFJvdyBNYWpvciBPcmRlcilcdWM1ZDAgXHVjMmI5XHVkNjU4XHVjNzc0XHVjNWQwXHVhYzhjIFx1YmNmNFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzJkY1x1Yjk3YyBcdWJhNTRcdWMyZGNcdWM5YzBcdWI4NWMgXHViY2Y0XHViMGI4XHViMmU0XHViYTc0IDAwMDAxMTAxMDAxMDExMDBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyYjlcdWQ2NThcdWM3NzRcdWFjMDAgXHViYzFiXHVjNzQwIFx1YmU0NFx1YmMwMCBcdWJhNTRcdWMyZGNcdWM5YzBcdWM2NDAgUlx1YWNmYyBDXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NFx1Yjk3YyBcdWFkZGNcdWQ2MDRcdWM3NzRcdWFjMDAgXHViY2Y0XHViMGI4IFx1YmIzOFx1Yzc5MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI4NWMgXHViY2MwXHVkNjU4XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbHQ7PSBUICZsdDs9IDEsMDAwKSBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFIsIFx1YWNmNVx1YmMzMSwgQywgXHVhY2Y1XHViYzMxLCBcdWMyYjlcdWQ2NThcdWM3NzRcdWFjMDAgXHViYzFiXHVjNzQwIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSZsdDs9UixDJmx0Oz0yMCkgXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IDBcdWFjZmMgMVx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVhZTM4XHVjNzc0XHViMjk0IFx1ZDU2ZFx1YzBjMSBSKkNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWRkY1x1ZDYwNFx1Yzc3NFx1YWMwMCBcdWJjZjRcdWIwYjRcdWI4MjRcdWFjZTAgXHViY2MwXHVkNjU4XHViNDE4XHVhZTMwIFx1YzgwNCBcdWJiMzhcdWM3OTAgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNmQwXHViNzk4IFx1YmIzOFx1Yzc5MCBcdWJhNTRcdWMyZGNcdWM5YzBcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YjA1ZFx1YjA5Y1x1YjJlNFx1YmE3NCwgXHVhZGY4IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVjODFjXHVhYzcwXHVkNTVjIFx1YjRhNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjcxNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRlY29kaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5DaGlwIGFuZCBEYWxlIGhhdmUgZGV2aXNlZCBhbiBlbmNyeXB0aW9uIG1ldGhvZCB0byBoaWRlIHRoZWlyICh3cml0dGVuKSB0ZXh0IG1lc3NhZ2VzLiBUaGV5IGZpcnN0IGFncmVlIHNlY3JldGx5IG9uIHR3byBudW1iZXJzIHRoYXQgd2lsbCBiZSB1c2VkIGFzIHRoZSBudW1iZXIgb2Ygcm93cyAoUikgYW5kIGNvbHVtbnMgKEMpIGluIGEgbWF0cml4LiBUaGUgc2VuZGVyIGVuY29kZXMgYW4gaW50ZXJtZWRpYXRlIGZvcm1hdCB1c2luZyB0aGUgZm9sbG93aW5nIHJ1bGVzOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRoZSB0ZXh0IGlzIGZvcm1lZCB3aXRoIHVwcGVyY2FzZSBsZXR0ZXJzIFtBLVpdIGFuZCAmbHQ7c3BhY2UmZ3Q7LjxcL2xpPlxyXG5cdDxsaT5FYWNoIHRleHQgY2hhcmFjdGVyIHdpbGwgYmUgcmVwcmVzZW50ZWQgYnkgZGVjaW1hbCB2YWx1ZXMgYXMgZm9sbG93czombmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD4mbHQ7c3BhY2UmZ3Q7ID0gMCwgQSA9IDEsIEIgPSAyLCBDID0gMywgLi4uLCBZID0gMjUsIFogPSAyNjxcL3A+XHJcblxyXG48cD5UaGUgc2VuZGVyIGVudGVycyB0aGUgNSBkaWdpdCBiaW5hcnkgcmVwcmVzZW50YXRpb24gb2YgdGhlIGNoYXJhY3RlcnMmcnNxdW87IHZhbHVlcyBpbiBhIHNwaXJhbCBwYXR0ZXJuIGFsb25nIHRoZSBtYXRyaXggYXMgc2hvd24gYmVsb3cuIFRoZSBtYXRyaXggaXMgcGFkZGVkIG91dCB3aXRoIHplcm9lcyAoMCkgdG8gZmlsbCB0aGUgbWF0cml4IGNvbXBsZXRlbHkuIEZvciBleGFtcGxlLCBpZiB0aGUgdGV4dCB0byBlbmNvZGUgaXM6ICZxdW90O0FDTSZxdW90OyBhbmQgUj00IGFuZCBDPTQsIHRoZSBtYXRyaXggd291bGQgYmUgZmlsbGVkIGluIGFzIGZvbGxvd3M6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvU2NyZWVuJTIwU2hvdCUyMDIwMTItMTAtMDYlMjBhdCUyMCVFQyU5OCVBNCVFQyVBMCU4NCUyMDEyXzM2XzM1LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4NXB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MTI2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QSA9IDAwMDAxLCBDID0gMDAwMTEsIE0gPSAwMTEwMSAob25lIGV4dHJhIDApJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBiaXRzIGluIHRoZSBtYXRyaXggYXJlIHRoZW4gY29uY2F0ZW5hdGVkIHRvZ2V0aGVyIGluIHJvdyBtYWpvciBvcmRlciBhbmQgc2VudCB0byB0aGUgcmVjZWl2ZXIuIFRoZSBleGFtcGxlIGFib3ZlIHdvdWxkIGJlIGVuY29kZWQgYXM6IDAwMDAxMTAxMDAxMDExMDA8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCkgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhc2V0cyB0aGF0IGZvbGxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBkYXRhc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQgY29udGFpbmluZyBSICgxJmx0Oz1SJmx0Oz0yMCksIGEgc3BhY2UsIEMgKDEmbHQ7PUMmbHQ7PTIwKSwgYSBzcGFjZSwgYW5kIGEgc3RyaW5nIG9mIGJpbmFyeSBkaWdpdHMgdGhhdCByZXByZXNlbnRzIHRoZSBjb250ZW50cyBvZiB0aGUgbWF0cml4IChSICogQyBiaW5hcnkgZGlnaXRzKS4gVGhlIGJpbmFyeSBkaWdpdHMgYXJlIGluIHJvdyBtYWpvciBvcmRlci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhc2V0LCB5b3Ugc2hvdWxkIGdlbmVyYXRlIG9uZSBsaW5lIG9mIG91dHB1dCB3aXRoIHRoZSBmb2xsb3dpbmcgdmFsdWVzOiBUaGUgZGF0YXNldCBudW1iZXIgYXMgYSBkZWNpbWFsIGludGVnZXIgKHN0YXJ0IGNvdW50aW5nIGF0IG9uZSksIGEgc3BhY2UsIGFuZCB0aGUgZGVjb2RlZCB0ZXh0IG1lc3NhZ2UuIFlvdSBzaG91bGQgdGhyb3cgYXdheSBhbnkgdHJhaWxpbmcgc3BhY2VzIGFuZFwvb3IgcGFydGlhbCBjaGFyYWN0ZXJzIGZvdW5kIHdoaWxlIGRlY29kaW5nPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d