시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1461 238 206 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+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWM4XHVjOWMwXHViOWM5IFx1ZDY4Y1x1YzgwNFx1YzVkMFx1YzExYyBcdWQ2NTRcdWMwYjRcdWQ0NWNcdWFjMDAgXHVhYzAwXHViOWFjXHVkMGE0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViYzE0XHVkMDM0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjE5M1x1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzViNFx1YjVhNCBcdWFlMDBcdWM3OTBcdWM3NzhcdWM5YzAgXHVhY2IwXHVjODE1XHVkNTU4XHVjOWMwIFx1YmFiYlx1ZDU1OFx1YjI5NCBcdWNlNzhcdWM3NDAgJiMzOTs/JiMzOTtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzBjMVx1YjM1NVx1Yzc3NFx1YWMwMCBcdWM4MDFcdWM1YjRcdWIxOTNcdWM3NDAgXHVjODg1XHVjNzc0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1ODlcdWM2YjRcdWM3NTggXHViYzE0XHVkMDM0XHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDshJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODQwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS09MTyIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gaGFzIHJlY2VudGx5IGJvdWdodCBhIHdoZWVsIG9mIGZvcnR1bmUuIEhlIHdyb3RlIGFuIHVwcGVyY2FzZSBsZXR0ZXIgb2YgRW5nbGlzaCBhbHBoYWJldCBvbnRvIGVhY2ggd2VkZ2UsIGxpa2UgdGhpczo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC93aGVlbC5wbmdcIiBzdHlsZT1cImhlaWdodDoyNzBweDsgd2lkdGg6MzQwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Tm8gbGV0dGVyIGFwcGVhcnMgdHdpY2UgaW4gdGhlIHdoZWVsLCBhbmQgdGhlIHdoZWVsIHNwaW5zIGluIGNsb2Nrd2lzZSBkaXJlY3Rpb24uIFRoZXJlIGlzIGEgcG9pbnRlciB0aGF0IHN0YXlzIGluIHRoZSBzYW1lIHBsYWNlIHdoaWxlIHRoZSB3aGVlbCBpcyBzcGlubmluZyAoaXQgaXMgcG9pbnRpbmcgdG8gSCBpbiB0aGUgcGljdHVyZSBhYm92ZSkuIFdoZW4gd2Ugc3BpbiB0aGUgd2hlZWwsIHRoZSBsZXR0ZXIgdG8gd2hpY2ggdGhlIHBvaW50ZXIgaXMgcG9pbnRpbmcgdG8gY2hhbmdlcyBhY2NvcmRpbmdseS48XC9wPlxyXG5cclxuPHA+TWlya28gc3Bpbm5lZCB0aGUgd2hlZWwgSyB0aW1lcyBpbiBhIHJvdywgYW5kIGVhY2ggdGltZSBoZSB3cm90ZSBkb3duIGhvdyBtYW55IHRpbWVzIHRoZSBwb2ludGVkIGxldHRlciBjaGFuZ2VkLCBhbmQgd2hhdCBsZXR0ZXIgd2FzIHBvaW50ZWQgdG8gYXQgdGhlIGVuZCBvZiB0aGF0IHNwaW4uPFwvcD5cclxuXHJcbjxwPlNsYXZrbyBmb3VuZCB0aGF0IHBhcGVyLCBhbmQgd291bGQgbGlrZSB0byBub3cgd2hhdCBsZXR0ZXJzIE1pcmtvIHdyb3RlIG9udG8gdGhlIHdlZGdlcyBvZiB0aGUgd2hlZWwuIEhlbHAgaGltIGRldGVybWluZSB0aGlzLCBpZiB0aGUgdG90YWwgbnVtYmVyIG9mIHdlZGdlcyBpcyBrbm93bi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXJzIE4gKDIgJmxlOyBOICZsZTsgMjUpLCB0aGUgbnVtYmVyIG9mIHdlZGdlcyBvbiB0aGUgd2hlZWwsIGFuZCBLICgxICZsZTsgSyAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2Ygc3BpbnMuPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgSyBsaW5lcyBjb250YWluIGRlc2NyaXB0aW9ucyBNaXJrbyB3cm90ZSBkb3duIGZvciBlYWNoIHNwaW4sIGluIG9yZGVyLiBFYWNoIGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBTICgxICZsZTsgUyAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIHBvaW50ZWQgbGV0dGVyIGNoYW5nZWQgZHVyaW5nIHRoYXQgc3BpbiwgYW5kIGFuIHVwcGVyY2FzZSBsZXR0ZXIgYXQgd2hpY2ggcG9pbnRlciBzdG9wcGVkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPklmIHRoZXJlIGlzIG5vIHdoZWVsIHRoYXQgbWVldHMgdGhlIHJlcXVpcmVtZW50cyBkZXNjcmliZWQsIG91dHB1dCAmbHNxdW87ISZyc3F1bzsuPFwvcD5cclxuXHJcbjxwPk90aGVyd2lzZSwgb3V0cHV0IHNlcXVlbmNlIG9mIGxldHRlcnMgd3JpdHRlbiBvbnRvIHRoZSB3aGVlbCwgc3RhcnRpbmcgZnJvbSB0aGUgcG9pbnRlZCBsZXR0ZXIgYXQgdGhlIGVuZCBvZiB0aGUgbGFzdCBzcGluIGFuZCBwcm9jZWVkaW5nIGNsb2Nrd2lzZS4gSWYgc29tZSBsZXR0ZXIgY2FuJnJzcXVvO3QgYmUgZGV0ZXJtaW5lZCwgb3V0cHV0ICZsc3F1bzs/JnJzcXVvOyBpbnN0ZWFkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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