시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1342 221 190 17.774%

문제

상덕이는 최근에 행운의 바퀴를 구매했다. 상덕이는 바퀴의 각 칸에 알파벳 대문자를 아래 그림과 같이 적었다.

바퀴에 같은 글자는 두 번 이상 등장하지 않는다. 또, 바퀴는 시계방향으로만 돌아간다. 바퀴 옆에는 화살표가 있는데, 이 화살표는 항상 한 곳을 가리키고 있으며, 돌아가는 동안 가리키는 글자는 바뀌게 된다. 위의 그림에서는 H를 가리키고 있다.

상덕이는 바퀴를 연속해서 K번 돌릴 것이다. 매번 바퀴를 돌릴 때 마다, 상덕이는 화살표가 가리키는 글자가 변하는 횟수와 어떤 글자에서 회전을 멈추었는지를 종이에 적는다.

희원이는 상덕이가 적어놓은 종이를 발견했다. 그 종이를 바탕으로 상덕이가 바퀴에 적은 알파벳을 알아내려고 한다.

상덕이가 종이에 적어놓은 내용과 바퀴의 칸의 수가 주어졌을 때, 바퀴에 적어놓은 알파벳을 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 바퀴의 칸의 수 N과 상덕이가 바퀴를 돌리는 횟수 K가 주어진다. (2 ≤ N ≤ 25, 1 ≤ K ≤ 100)

다음 줄부터 K줄에는 바퀴를 회전시켰을 때 화살표가 가리키는 글자가 몇 번 바뀌었는지를 나타내는 S와 회전을 멈추었을 때 가리키던 글자가 주어진다. (1 ≤ S ≤ 100)

출력

첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이 때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없다면 "!"를 출력한다. 

예제 입력 1

8 8
4 V
3 I
7 T
7 A
6 R
5 N
1 O
9 H

예제 출력 1

HONITAVR

힌트

W3sicHJvYmxlbV9pZCI6IjI4NDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWM2YjRcdWM3NTggXHViYzE0XHVkMDM0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHVjZDVjXHVhZGZjXHVjNWQwIFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWJjMTRcdWQwMzRcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHViYzE0XHVkMDM0XHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MDFcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvd2hlZWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjcwcHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmMxNFx1ZDAzNFx1YzVkMCBcdWFjMTlcdWM3NDAgXHVhZTAwXHVjNzkwXHViMjk0IFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjYxMCwgXHViYzE0XHVkMDM0XHViMjk0IFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1Y1x1YjljYyBcdWIzY2NcdWM1NDRcdWFjMDRcdWIyZTQuIFx1YmMxNFx1ZDAzNCBcdWM2MDZcdWM1ZDBcdWIyOTQgXHVkNjU0XHVjMGI0XHVkNDVjXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVkNTVjIFx1YWNmM1x1Yzc0NCBcdWFjMDBcdWI5YWNcdWQwYTRcdWFjZTAgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWIzY2NcdWM1NDRcdWFjMDBcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWFlMDBcdWM3OTBcdWIyOTQgXHViYzE0XHViMDBjXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExY1x1YjI5NCBIXHViOTdjIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YjM1NVx1Yzc3NFx1YjI5NCBcdWJjMTRcdWQwMzRcdWI5N2MgXHVjNWYwXHVjMThkXHVkNTc0XHVjMTFjIEtcdWJjODggXHViM2NjXHViOWI0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWU0XHViYzg4IFx1YmMxNFx1ZDAzNFx1Yjk3YyBcdWIzY2NcdWI5YjQgXHViNTRjIFx1YjljOFx1YjJlNCwgXHVjMGMxXHViMzU1XHVjNzc0XHViMjk0IFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YWMwMCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YmNjMFx1ZDU1OFx1YjI5NCBcdWQ2OWZcdWMyMThcdWM2NDAgXHVjNWI0XHViNWE0IFx1YWUwMFx1Yzc5MFx1YzVkMFx1YzExYyBcdWQ2OGNcdWM4MDRcdWM3NDQgXHViYTQ4XHVjZDk0XHVjNWM4XHViMjk0XHVjOWMwXHViOTdjIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDc2Y1x1YzZkMFx1Yzc3NFx1YjI5NCBcdWMwYzFcdWIzNTVcdWM3NzRcdWFjMDAgXHVjODAxXHVjNWI0XHViMTkzXHVjNzQwIFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWJjMWNcdWFjYWNcdWQ1ODhcdWIyZTQuIFx1YWRmOCBcdWM4ODVcdWM3NzRcdWI5N2MgXHViYzE0XHVkMGQ1XHVjNzNjXHViODVjIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWJjMTRcdWQwMzRcdWM1ZDAgXHVjODAxXHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWIzNTVcdWM3NzRcdWFjMDAgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjE5M1x1Yzc0MCBcdWIwYjRcdWM2YTlcdWFjZmMgXHViYzE0XHVkMDM0XHVjNzU4IFx1Y2U3OFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYzE0XHVkMDM0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjE5M1x1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmMxNFx1ZDAzNFx1Yzc1OCBcdWNlNzhcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1YmMxNFx1ZDAzNFx1Yjk3YyBcdWIzY2NcdWI5YWNcdWIyOTQgXHVkNjlmXHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyNSwgMSAmbGU7IEsgJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgS1x1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMTRcdWQwMzRcdWI5N2MgXHVkNjhjXHVjODA0XHVjMmRjXHVjZjMwXHVjNzQ0IFx1YjU0YyBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWJhODcgXHViYzg4IFx1YmMxNFx1YjAwY1x1YzVjOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgU1x1YzY0MCBcdWQ2OGNcdWM4MDRcdWM3NDQgXHViYTQ4XHVjZDk0XHVjNWM4XHVjNzQ0IFx1YjU0YyBcdWFjMDBcdWI5YWNcdWQwYTRcdWIzNTggXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBTICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHVjOWMwXHViOWM5IFx1ZDY4Y1x1YzgwNFx1YzVkMFx1YzExYyBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViYzE0XHVkMDM0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjE5M1x1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWM1YjRcdWI1YTQgXHVhZTAwXHVjNzkwXHVjNzc4XHVjOWMwIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjZTc4XHVjNzQwICYjMzk7PyYjMzk7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWMwYzFcdWIzNTVcdWM3NzRcdWFjMDAgXHVjODAxXHVjNWI0XHViMTkzXHVjNzQwIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVkNTg5XHVjNmI0XHVjNzU4IFx1YmMxNFx1ZDAzNFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQgJnF1b3Q7ISZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg0MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktPTE8iLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGhhcyByZWNlbnRseSBib3VnaHQgYSB3aGVlbCBvZiBmb3J0dW5lLiBIZSB3cm90ZSBhbiB1cHBlcmNhc2UgbGV0dGVyIG9mIEVuZ2xpc2ggYWxwaGFiZXQgb250byBlYWNoIHdlZGdlLCBsaWtlIHRoaXM6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvd2hlZWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjcwcHg7IHdpZHRoOjM0MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vIGxldHRlciBhcHBlYXJzIHR3aWNlIGluIHRoZSB3aGVlbCwgYW5kIHRoZSB3aGVlbCBzcGlucyBpbiBjbG9ja3dpc2UgZGlyZWN0aW9uLiBUaGVyZSBpcyBhIHBvaW50ZXIgdGhhdCBzdGF5cyBpbiB0aGUgc2FtZSBwbGFjZSB3aGlsZSB0aGUgd2hlZWwgaXMgc3Bpbm5pbmcgKGl0IGlzIHBvaW50aW5nIHRvIEggaW4gdGhlIHBpY3R1cmUgYWJvdmUpLiBXaGVuIHdlIHNwaW4gdGhlIHdoZWVsLCB0aGUgbGV0dGVyIHRvIHdoaWNoIHRoZSBwb2ludGVyIGlzIHBvaW50aW5nIHRvIGNoYW5nZXMgYWNjb3JkaW5nbHkuPFwvcD5cclxuXHJcbjxwPk1pcmtvIHNwaW5uZWQgdGhlIHdoZWVsIEsgdGltZXMgaW4gYSByb3csIGFuZCBlYWNoIHRpbWUgaGUgd3JvdGUgZG93biBob3cgbWFueSB0aW1lcyB0aGUgcG9pbnRlZCBsZXR0ZXIgY2hhbmdlZCwgYW5kIHdoYXQgbGV0dGVyIHdhcyBwb2ludGVkIHRvIGF0IHRoZSBlbmQgb2YgdGhhdCBzcGluLjxcL3A+XHJcblxyXG48cD5TbGF2a28gZm91bmQgdGhhdCBwYXBlciwgYW5kIHdvdWxkIGxpa2UgdG8gbm93IHdoYXQgbGV0dGVycyBNaXJrbyB3cm90ZSBvbnRvIHRoZSB3ZWRnZXMgb2YgdGhlIHdoZWVsLiBIZWxwIGhpbSBkZXRlcm1pbmUgdGhpcywgaWYgdGhlIHRvdGFsIG51bWJlciBvZiB3ZWRnZXMgaXMga25vd24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOICgyICZsZTsgTiAmbGU7IDI1KSwgdGhlIG51bWJlciBvZiB3ZWRnZXMgb24gdGhlIHdoZWVsLCBhbmQgSyAoMSAmbGU7IEsgJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHNwaW5zLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIEsgbGluZXMgY29udGFpbiBkZXNjcmlwdGlvbnMgTWlya28gd3JvdGUgZG93biBmb3IgZWFjaCBzcGluLCBpbiBvcmRlci4gRWFjaCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgUyAoMSAmbGU7IFMgJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoZSBwb2ludGVkIGxldHRlciBjaGFuZ2VkIGR1cmluZyB0aGF0IHNwaW4sIGFuZCBhbiB1cHBlcmNhc2UgbGV0dGVyIGF0IHdoaWNoIHBvaW50ZXIgc3RvcHBlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGVyZSBpcyBubyB3aGVlbCB0aGF0IG1lZXRzIHRoZSByZXF1aXJlbWVudHMgZGVzY3JpYmVkLCBvdXRwdXQgJmxzcXVvOyEmcnNxdW87LjxcL3A+XHJcblxyXG48cD5PdGhlcndpc2UsIG91dHB1dCBzZXF1ZW5jZSBvZiBsZXR0ZXJzIHdyaXR0ZW4gb250byB0aGUgd2hlZWwsIHN0YXJ0aW5nIGZyb20gdGhlIHBvaW50ZWQgbGV0dGVyIGF0IHRoZSBlbmQgb2YgdGhlIGxhc3Qgc3BpbiBhbmQgcHJvY2VlZGluZyBjbG9ja3dpc2UuIElmIHNvbWUgbGV0dGVyIGNhbiZyc3F1bzt0IGJlIGRldGVybWluZWQsIG91dHB1dCAmbHNxdW87PyZyc3F1bzsgaW5zdGVhZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 2번