시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 334 120 109 41.923%

문제

선영이는 다가오는 COCI에 사용할 데이터를 만드느라 삼일동안 깨어있었다. 더 이상 데이터를 만들 수 없는 상황에 이르렀고, 심지어 선영이는 신경쇠약에 걸려 아무것도 제대로 보지 못하는 상황이 되었다.

선영이가 무엇인가를 읽다가 눈을 한 번 깜박하면 단어의 뒷 부분 절반이 앞 부분과 섞이게 된다. (길이가 홀수인 경우에는 뒷 부분의 길이가 짧다) 섞이는 방법은 아래와 같다.

  • 마지막 글자가 첫 번째 글자와 두 번째 글자 사이로 이동한다.
  • 뒤에서 두 번째 글자가 두 번째 글자와 세 번째 글자 사이로 이동한다.
  • 뒤에서 k번째 글자는 앞에서부터 k번째와 k+1번째 글자 사이로 이동한다.

에를 들어, 선영이가 "abcdef"란 단어를 보다가 눈을 한 번 깜박이면, 단어가 "afbecd"가 된다. 여기서 한 번 더 깜박이면 "adfcbe"가 된다.

선영이는 한 단어를 쓰고난 이후에 눈을 X번 깜박였고, 처음에 작성한 단어가 무엇인지 궁금해졌다. X와 눈을 X번 깜박인 후에 선영이가 보고 있는 단어가 주어졌을 때, 원래 단어가 무엇이었는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다.

출력

첫째 줄에 X번 깜박이기 전 단어를 출력한다.

예제 입력 1

4
acefdb

예제 출력 1

abcdef

힌트

단어는 다음과 같이 변한다. abcdef, afbecd, adfcbe, aedbfc, acefdb

W3sicHJvYmxlbV9pZCI6Ijk1MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4NzhcdWI4MjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWFjMDBcdWM2MjRcdWIyOTQgQ09DSVx1YzVkMCBcdWMwYWNcdWM2YTlcdWQ1NjAgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5MFx1Yjc3YyBcdWMwYmNcdWM3N2NcdWIzZDlcdWM1NDggXHVhZTY4XHVjNWI0XHVjNzg4XHVjNWM4XHViMmU0LiBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWMwYzFcdWQ2NjlcdWM1ZDAgXHVjNzc0XHViOTc0XHViODAwXHVhY2UwLCBcdWMyZWNcdWM5YzBcdWM1YjQgXHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YzJlMFx1YWNiZFx1YzFlMFx1YzU3ZFx1YzVkMCBcdWFjNzhcdWI4MjQgXHVjNTQ0XHViYjM0XHVhYzgzXHViM2M0IFx1YzgxY1x1YjMwMFx1Yjg1YyBcdWJjZjRcdWM5YzAgXHViYWJiXHVkNTU4XHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWJiMzRcdWM1YzdcdWM3NzhcdWFjMDBcdWI5N2MgXHVjNzdkXHViMmU0XHVhYzAwIFx1YjIwOFx1Yzc0NCBcdWQ1NWMgXHViYzg4IFx1YWU1Y1x1YmMxNVx1ZDU1OFx1YmE3NCBcdWIyZThcdWM1YjRcdWM3NTggXHViNGI3IFx1YmQ4MFx1YmQ4NCBcdWM4MDhcdWJjMThcdWM3NzQgXHVjNTVlIFx1YmQ4MFx1YmQ4NFx1YWNmYyBcdWMxMWVcdWM3NzRcdWFjOGMgXHViNDFjXHViMmU0LiAoXHVhZTM4XHVjNzc0XHVhYzAwIFx1ZDY0MFx1YzIxOFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViNGI3IFx1YmQ4MFx1YmQ4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjOWU3XHViMmU0KSBcdWMxMWVcdWM3NzRcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViOWM4XHVjOWMwXHViOWM5IFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MFx1YzY0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWUwMFx1Yzc5MCBcdWMwYWNcdWM3NzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0YTRcdWM1ZDBcdWMxMWMgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWFjMDAgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTBcdWM2NDAgXHVjMTM4IFx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTAgXHVjMGFjXHVjNzc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNGE0XHVjNWQwXHVjMTFjIGtcdWJjODhcdWM5ZjggXHVhZTAwXHVjNzkwXHViMjk0IFx1YzU1ZVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBrXHViYzg4XHVjOWY4XHVjNjQwIGsrMVx1YmM4OFx1YzlmOCBcdWFlMDBcdWM3OTAgXHVjMGFjXHVjNzc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM1ZDBcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWMxMjBcdWM2MDFcdWM3NzRcdWFjMDAgJnF1b3Q7YWJjZGVmJnF1b3Q7XHViNzgwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWJjZjRcdWIyZTRcdWFjMDAgXHViMjA4XHVjNzQ0IFx1ZDU1YyBcdWJjODggXHVhZTVjXHViYzE1XHVjNzc0XHViYTc0LCBcdWIyZThcdWM1YjRcdWFjMDAgJnF1b3Q7YWZiZWNkJnF1b3Q7XHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1ZDU1YyBcdWJjODggXHViMzU0IFx1YWU1Y1x1YmMxNVx1Yzc3NFx1YmE3NCAmcXVvdDthZGZjYmUmcXVvdDtcdWFjMDAgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVkNTVjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWM0ZjBcdWFjZTBcdWIwOWMgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YjIwOFx1Yzc0NCBYXHViYzg4IFx1YWU1Y1x1YmMxNVx1YzYwMFx1YWNlMCwgXHVjYzk4XHVjNzRjXHVjNWQwIFx1Yzc5MVx1YzEzMVx1ZDU1YyBcdWIyZThcdWM1YjRcdWFjMDAgXHViYjM0XHVjNWM3XHVjNzc4XHVjOWMwIFx1YWQ4MVx1YWUwOFx1ZDU3NFx1Yzg0Y1x1YjJlNC4gWFx1YzY0MCBcdWIyMDhcdWM3NDQgWFx1YmM4OCBcdWFlNWNcdWJjMTVcdWM3NzggXHVkNmM0XHVjNWQwIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWJjZjRcdWFjZTAgXHVjNzg4XHViMjk0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM2ZDBcdWI3OTggXHViMmU4XHVjNWI0XHVhYzAwIFx1YmIzNFx1YzVjN1x1Yzc3NFx1YzVjOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgWCgxICZsZTsgWCAmbGU7IDEsMDAwLDAwMCwwMDApIFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgWFx1YmM4OCBcdWFlNWNcdWJjMTVcdWM3NzggXHVkNmM0XHVjNzU4IFx1YjJlOFx1YzViNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWFkNmNcdWFjMDQgWzMsMTAwMF1cdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgWFx1YmM4OCBcdWFlNWNcdWJjMTVcdWM3NzRcdWFlMzAgXHVjODA0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjJlOFx1YzViNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1Y1x1YjJlNC4gYWJjZGVmLCBhZmJlY2QsIGFkZmNiZSwgYWVkYmZjLCBhY2VmZGI8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk1MTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTTE9NIiwiZGVzY3JpcHRpb24iOiI8cD5MaXR0bGUgTWFyaW4gc3BlbnQgYWxsIGhpcyBkYXkgZ2VuZXJhdGluZyB0ZXN0IGRhdGEgZm9yIENPQ0kuIEhlIHNpbXBseSBjb3VsZG4mIzM5O3QgbWFrZSBpdCB3b3JrLCBzbyBoZSBoYWQgYSBuZXJ2b3VzIGJyZWFrZG93biBhbmQgY2FuJiMzOTt0IGV2ZW4gc2VlIGNsZWFybHkgYW55bW9yZS4gRXZlcnkgdGltZSBoZSBibGlua3Mgd2hpbGUgcmVhZGluZywgdGhlIGxldHRlcnMgaW4gYSB3b3JkIGdldCBtaXhlZCB1cCBzbyB0aGF0IHRoZSBsZXR0ZXJzIGZyb20gdGhlIHNlY29uZCBoYWxmIG9mIHRoZSB3b3JkICh0aGUgc2hvcnRlciBoYWxmLCBpZiB0aGUgbGVuZ3RoIGlzIGFuIG9kZCBudW1iZXIpICZxdW90O2p1bXAgaW4mcXVvdDsgYmV0d2VlbiB0aGUgbGV0dGVycyBmcm9tIHRoZSBmaXJzdCBoYWxmIGluIHRoZSBmb2xsb3dpbmcgd2F5OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnRoZSBsYXN0IGxldHRlciAmcXVvdDtqdW1wcyBpbiZxdW90OyBiZXR3ZWVuIHRoZSBmaXJzdCBhbmQgdGhlIHNlY29uZCBsZXR0ZXImbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIHBlbnVsdGltYXRlIGxldHRlciAmcXVvdDtqdW1wcyBpbiZxdW90OyBiZXR3ZWVuIHRoZSBzZWNvbmQgYW5kIHRoZSB0aGlyZCBsZXR0ZXImbmJzcDs8XC9saT5cclxuXHQ8bGk+dGhlIGs8c3VwPnRoPFwvc3VwPiBsZXR0ZXIgZnJvbSB0aGUgZW5kICZxdW90O2p1bXBzIGluJnF1b3Q7IGJldHdlZW4gdGhlIGs8c3VwPnRoPFwvc3VwPiBhbmQgdGhlIChrKzEpPHN1cD50aDxcL3N1cD4gbGV0dGVyIGZyb20gdGhlIGJlZ2lubmluZyZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgd29yZCAmcXVvdDthYmNkZWYmcXVvdDsgd291bGQgYmVjb21lICZxdW90O2FmYmVjZCZxdW90OyBhZnRlciBibGlua2luZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SWYgTWFyaW4gYmxpbmtzIGFnYWluLCB0aGUgc2FtZSB0aGluZyBoYXBwZW5zLiBBZnRlciB0d28gYmxpbmtzLCB0aGUgd29yZCAmcXVvdDthYmNkZWYmcXVvdDsgYmVjb21lcyAmcXVvdDthZGZjYmUmcXVvdDsuJm5ic3A7PGJyIFwvPlxyXG4mbmJzcDs8YnIgXC8+XHJcbk1hcmluIGhhcyBkZWNpZGVkIHRvIHdyaXRlIGEgcHJvZ3JhbSB0byBoZWxwIGhpbSBkZXRlcm1pbmUgd2hhdCYjMzk7cyBleGFjdGx5IHdyaXR0ZW4gb24gdGhlIHNjcmVlbi4gVW5mb3J0dW5hdGVseSwgYWZ0ZXIgYSBkYXkmIzM5O3Mgd29yaywgaGUmIzM5O3Mgc2ltcGx5IHRvbyB0aXJlZCBhbmQgaGUgbmVlZHMgeW91ciBoZWxwLiBZb3UgYXJlIGdpdmVuIFgsIHRoZSBudW1iZXIgb2YgYmxpbmtzLCBhbmQgdGhlIHdvcmQgTWFyaW4gc2VlcyBvbiB0aGUgc2NyZWVuLiBXcml0ZSBhIHByb2dyYW0gdG8gc29sdmUgdGhlIG15c3RlcnkgZm9yIE1hcmluIGFuZCBkZXRlcm1pbmUgd2hhdCB3YXMgYWN0dWFsbHkgdGhlIHdvcmQgYmVmb3JlIGhlIGJsaW5rZWQgWCB0aW1lcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcG9zaXRpdmUgaW50ZWdlciBYICgxICZsZTsgWCAmbGU7IDEgMDAwIDAwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHRpbWVzIE1hcmluIGJsaW5rZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgd29yZCBmcm9tIHRoZSBzY3JlZW4sIGl0cyBsZW5ndGggYmVpbmcgZnJvbSB0aGUgaW50ZXJ2YWwgWzMsIDEwMDBdLiBUaGUgd29yZCB3aWxsIGNvbnNpc3Qgb25seSBmcm9tIHNtYWxsIGxldHRlcnMgb2YgRW5nbGlzaCBhbHBoYWJldC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSBvcmlnaW5hbCB3b3JkLCBiZWZvcmUgTWFyaW4gYmxpbmtlZCBYIHRpbWVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHdvcmQgZ2V0cyBhbHRlcmVkIGluIHRoZSBmb2xsb3dpbmcgb3JkZXI6IGFiY2RlZiwgYWZiZWNkLCBhZGZjYmUsIGFlZGJmYywgYWNlZmRiLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d