시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB398476162319.300%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 3
1 A
2 B
3 C

예제 출력 1

!

예제 입력 2

5 6
1 A
2 B
5 B
1 C
2 A
2 B

예제 출력 2

B?A?C

예제 입력 3

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

예제 출력 3

HONITAVR
W3sicHJvYmxlbV9pZCI6IjI4NDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWM2YjRcdWM3NTggXHViYzE0XHVkMDM0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHVjZDVjXHVhZGZjXHVjNWQwIFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWJjMTRcdWQwMzRcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHViYzE0XHVkMDM0XHVjNzU4IFx1YWMwMSBcdWNlNzhcdWM1ZDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM4MDFcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZDgxMzBmN2QtZjJhOC00MzE3LTliNWMtMGYxODlhNjYxMzY1XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyODNweDsgaGVpZ2h0OiAyNTNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViYzE0XHVkMDM0XHVjNWQwIFx1YWMxOVx1Yzc0MCBcdWFlMDBcdWM3OTBcdWIyOTQgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViNGYxXHVjN2E1XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCBcdWJjMTRcdWQwMzRcdWIyOTQgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjXHViOWNjIFx1YjNjY1x1YzU0NFx1YWMwNFx1YjJlNC4gXHViYzE0XHVkMDM0IFx1YzYwNlx1YzVkMFx1YjI5NCBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVkNjU0XHVjMGI0XHVkNDVjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWQ1NWMgXHVhY2YzXHVjNzQ0IFx1YWMwMFx1YjlhY1x1ZDBhNFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjNjY1x1YzU0NFx1YWMwMFx1YjI5NCBcdWIzZDlcdWM1NDggXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWJjMTRcdWIwMGNcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM3MDRcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjXHViMjk0IEhcdWI5N2MgXHVhYzAwXHViOWFjXHVkMGE0XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHViMzU1XHVjNzc0XHViMjk0IFx1YmMxNFx1ZDAzNFx1Yjk3YyBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWMxMWMgS1x1YmM4OCBcdWIzY2NcdWI5YjQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI5ZTRcdWJjODggXHViYzE0XHVkMDM0XHViOTdjIFx1YjNjY1x1YjliNCBcdWI1NGMgXHViOWM4XHViMmU0LCBcdWMwYzFcdWIzNTVcdWM3NzRcdWIyOTQgXHVkNjU0XHVjMGI0XHVkNDVjXHVhYzAwIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjI5NCBcdWFlMDBcdWM3OTBcdWFjMDAgXHViY2MwXHVkNTU4XHViMjk0IFx1ZDY5Zlx1YzIxOFx1YzY0MCBcdWM1YjRcdWI1YTQgXHVhZTAwXHVjNzkwXHVjNWQwXHVjMTFjIFx1ZDY4Y1x1YzgwNFx1Yzc0NCBcdWJhNDhcdWNkOTRcdWM1YzhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNzZjXHVjNmQwXHVjNzc0XHViMjk0IFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIxOTNcdWM3NDAgXHVjODg1XHVjNzc0XHViOTdjIFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHVhZGY4IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1YmMxNFx1ZDAzNFx1YzVkMCBcdWM4MDFcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVjNWI0XHViMTkzXHVjNzQwIFx1YjBiNFx1YzZhOVx1YWNmYyBcdWJjMTRcdWQwMzRcdWM3NTggXHVjZTc4XHVjNzU4IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWJjMTRcdWQwMzRcdWM1ZDAgXHVjODAxXHVjNWI0XHViMTkzXHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzE0XHVkMDM0XHVjNzU4IFx1Y2U3OFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWMwYzFcdWIzNTVcdWM3NzRcdWFjMDAgXHViYzE0XHVkMDM0XHViOTdjIFx1YjNjY1x1YjlhY1x1YjI5NCBcdWQ2OWZcdWMyMTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDI1LCAxICZsZTsgSyAmbGU7IDEwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBLXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxNFx1ZDAzNFx1Yjk3YyBcdWQ2OGNcdWM4MDRcdWMyZGNcdWNmMzBcdWM3NDQgXHViNTRjIFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YWMwMCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YmE4NyBcdWJjODggXHViYzE0XHViMDBjXHVjNWM4XHViMjk0XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBTXHVjNjQwIFx1ZDY4Y1x1YzgwNFx1Yzc0NCBcdWJhNDhcdWNkOTRcdWM1YzhcdWM3NDQgXHViNTRjIFx1YWMwMFx1YjlhY1x1ZDBhNFx1YjM1OCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFMgJmxlOyAxMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNjhjXHVjODA0XHVjNWQwXHVjMTFjIFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YWMwMCBcdWFjMDBcdWI5YWNcdWQwYTRcdWIyOTQgXHViYjM4XHVjNzkwXHViZDgwXHVkMTMwIFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWJjMTRcdWQwMzRcdWM1ZDAgXHVjODAxXHVjNWI0XHViMTkzXHVjNzQwIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNWI0XHViNWE0IFx1YWUwMFx1Yzc5MFx1Yzc3OFx1YzljMCBcdWFjYjBcdWM4MTVcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1Y2U3OFx1Yzc0MCAmIzM5Oz8mIzM5O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjMGMxXHViMzU1XHVjNzc0XHVhYzAwIFx1YzgwMVx1YzViNFx1YjE5M1x1Yzc0MCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWJjMTRcdWQwMzRcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0ICZxdW90OyEmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4NDAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJLT0xPIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgcmVjZW50bHkgYm91Z2h0IGEgd2hlZWwgb2YgZm9ydHVuZS4gSGUgd3JvdGUgYW4gdXBwZXJjYXNlIGxldHRlciBvZiBFbmdsaXNoIGFscGhhYmV0IG9udG8gZWFjaCB3ZWRnZSwgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2Q4MTMwZjdkLWYyYTgtNDMxNy05YjVjLTBmMTg5YTY2MTM2NVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMjgzcHg7IGhlaWdodDogMjUzcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPk5vIGxldHRlciBhcHBlYXJzIHR3aWNlIGluIHRoZSB3aGVlbCwgYW5kIHRoZSB3aGVlbCBzcGlucyBpbiBjbG9ja3dpc2UgZGlyZWN0aW9uLiBUaGVyZSBpcyBhIHBvaW50ZXIgdGhhdCBzdGF5cyBpbiB0aGUgc2FtZSBwbGFjZSB3aGlsZSB0aGUgd2hlZWwgaXMgc3Bpbm5pbmcgKGl0IGlzIHBvaW50aW5nIHRvIEggaW4gdGhlIHBpY3R1cmUgYWJvdmUpLiBXaGVuIHdlIHNwaW4gdGhlIHdoZWVsLCB0aGUgbGV0dGVyIHRvIHdoaWNoIHRoZSBwb2ludGVyIGlzIHBvaW50aW5nIHRvIGNoYW5nZXMgYWNjb3JkaW5nbHkuPFwvcD5cclxuXHJcbjxwPk1pcmtvIHNwaW5uZWQgdGhlIHdoZWVsIEsgdGltZXMgaW4gYSByb3csIGFuZCBlYWNoIHRpbWUgaGUgd3JvdGUgZG93biBob3cgbWFueSB0aW1lcyB0aGUgcG9pbnRlZCBsZXR0ZXIgY2hhbmdlZCwgYW5kIHdoYXQgbGV0dGVyIHdhcyBwb2ludGVkIHRvIGF0IHRoZSBlbmQgb2YgdGhhdCBzcGluLjxcL3A+XHJcblxyXG48cD5TbGF2a28gZm91bmQgdGhhdCBwYXBlciwgYW5kIHdvdWxkIGxpa2UgdG8gbm93IHdoYXQgbGV0dGVycyBNaXJrbyB3cm90ZSBvbnRvIHRoZSB3ZWRnZXMgb2YgdGhlIHdoZWVsLiBIZWxwIGhpbSBkZXRlcm1pbmUgdGhpcywgaWYgdGhlIHRvdGFsIG51bWJlciBvZiB3ZWRnZXMgaXMga25vd24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBpbnRlZ2VycyBOICgyICZsZTsgTiAmbGU7IDI1KSwgdGhlIG51bWJlciBvZiB3ZWRnZXMgb24gdGhlIHdoZWVsLCBhbmQgSyAoMSAmbGU7IEsgJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHNwaW5zLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIEsgbGluZXMgY29udGFpbiBkZXNjcmlwdGlvbnMgTWlya28gd3JvdGUgZG93biBmb3IgZWFjaCBzcGluLCBpbiBvcmRlci4gRWFjaCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgUyAoMSAmbGU7IFMgJmxlOyAxMDApLCB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoZSBwb2ludGVkIGxldHRlciBjaGFuZ2VkIGR1cmluZyB0aGF0IHNwaW4sIGFuZCBhbiB1cHBlcmNhc2UgbGV0dGVyIGF0IHdoaWNoIHBvaW50ZXIgc3RvcHBlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGVyZSBpcyBubyB3aGVlbCB0aGF0IG1lZXRzIHRoZSByZXF1aXJlbWVudHMgZGVzY3JpYmVkLCBvdXRwdXQgJmxzcXVvOyEmcnNxdW87LjxcL3A+XHJcblxyXG48cD5PdGhlcndpc2UsIG91dHB1dCBzZXF1ZW5jZSBvZiBsZXR0ZXJzIHdyaXR0ZW4gb250byB0aGUgd2hlZWwsIHN0YXJ0aW5nIGZyb20gdGhlIHBvaW50ZWQgbGV0dGVyIGF0IHRoZSBlbmQgb2YgdGhlIGxhc3Qgc3BpbiBhbmQgcHJvY2VlZGluZyBjbG9ja3dpc2UuIElmIHNvbWUgbGV0dGVyIGNhbiZyc3F1bzt0IGJlIGRldGVybWluZWQsIG91dHB1dCAmbHNxdW87PyZyc3F1bzsgaW5zdGVhZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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