시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 808 346 282 43.185%

문제

개미가 일렬로 이동할 때, 가장 앞의 개미를 제외한 나머지 개미는 모두 앞에 개미가 한 마리씩 있다. 

서로 반대 방향으로 이동하던 두 개미 그룹이 좁은 길에서 만났을 때, 개미는 어떻게 지나갈까?

최근 연구에 의하면 위와 같은 상황이 벌어지면 개미는 서로를 점프해서 넘어간다고 한다.

즉, 두 그룹이 만났을 때, 1초에 한번씩 개미는 서로를 뛰어 넘는다. (한 개미가 다른 개미를 뛰어 넘고, 다른 개미는 그냥 전진한다고 생각해도 된다)

하지만 모든 개미가 점프를 하는 것은 아니다. 자신의 앞에 반대 방향으로 움직이던 개미가 있는 경우에만 점프를 하게 된다.

첫 번째 그룹이 ABC로 움직이고, 두 번째 그룹의 개미가 DEF순으로 움직인다고 하자. 그럼, 좁은 길에서 만났을 때, 개미의 순서는 CBADEF가 된다. 1초가 지났을 때는 자신의 앞에 반대방향으로 움직이는 개미가 있는 개미는 A와 D다. 따라서, 개미의 순서는 CBDAEF가 된다. 2초가 되었을 때, 자신의 앞에 반대 방향으로 움직이는 개미는 B,D,A,E가 있다. 따라서, 개미의 순서는 CDBEAF가 된다.

T초가 지난 후에 개미의 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 첫 번째 그룹의 개미의 수 N1과 두 번째 그룹의 개미의 수 N2가 주어진다.

다음 두 개 줄에는 첫 번째 그룹과 두 번째 그룹의 개미의 순서가 주어진다. 각 개미는 알파벳 대문자로 표현할 수 있으며, 두 그룹에서 중복되는 알파벳은 없다.

마지막 줄에는 T가 주어진다. (0 ≤ T ≤ 50)

출력

T초가 지난 후에 개미의 순서를 출력한다. 첫 번째 개미 그룹은 왼쪽에서 오른쪽으로 움직이고, 두 번째 그룹은 반대 방향으로 움직인다.

예제 입력 1

3 3
ABC
DEF
2

예제 출력 1

CDBEAF
W3sicHJvYmxlbV9pZCI6IjMwNDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWJiZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxY1x1YmJmOFx1YWMwMCBcdWM3N2NcdWI4MmNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1Yzc1OCBcdWFjMWNcdWJiZjhcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFjMWNcdWJiZjhcdWIyOTQgXHViYWE4XHViNDUwIFx1YzU1ZVx1YzVkMCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVkNTVjIFx1YjljOFx1YjlhY1x1YzUyOSBcdWM3ODhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1YyBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjM1OCBcdWI0NTAgXHVhYzFjXHViYmY4IFx1YWRmOFx1YjhmOVx1Yzc3NCBcdWM4ODFcdWM3NDAgXHVhZTM4XHVjNWQwXHVjMTFjIFx1YjljY1x1YjBhY1x1Yzc0NCBcdWI1NGMsIFx1YWMxY1x1YmJmOFx1YjI5NCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVjOWMwXHViMDk4XHVhYzA4XHVhZTRjPzxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWFkZmMgXHVjNWYwXHVhZDZjXHVjNWQwIFx1Yzc1OFx1ZDU1OFx1YmE3NCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzBjMVx1ZDY2OVx1Yzc3NCBcdWJjOGNcdWM1YjRcdWM5YzBcdWJhNzQgXHVhYzFjXHViYmY4XHViMjk0IFx1YzExY1x1Yjg1Y1x1Yjk3YyBcdWM4MTBcdWQ1MDRcdWQ1NzRcdWMxMWMgXHViMTE4XHVjNWI0XHVhYzA0XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTg5LCBcdWI0NTAgXHVhZGY4XHViOGY5XHVjNzc0IFx1YjljY1x1YjBhY1x1Yzc0NCBcdWI1NGMsIDFcdWNkMDhcdWM1ZDAgXHVkNTVjXHViYzg4XHVjNTI5IFx1YWMxY1x1YmJmOFx1YjI5NCBcdWMxMWNcdWI4NWNcdWI5N2MgXHViNmYwXHVjNWI0IFx1YjExOFx1YjI5NFx1YjJlNC4gKFx1ZDU1YyBcdWFjMWNcdWJiZjhcdWFjMDAgXHViMmU0XHViOTc4IFx1YWMxY1x1YmJmOFx1Yjk3YyBcdWI2ZjBcdWM1YjQgXHViMTE4XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVhYzFjXHViYmY4XHViMjk0IFx1YWRmOFx1YjBlNSBcdWM4MDRcdWM5YzRcdWQ1NWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjIFx1YmFhOFx1YjRlMCBcdWFjMWNcdWJiZjhcdWFjMDAgXHVjODEwXHVkNTA0XHViOTdjIFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNTVlXHVjNWQwIFx1YmMxOFx1YjMwMCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMzU4IFx1YWMxY1x1YmJmOFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViOWNjIFx1YzgxMFx1ZDUwNFx1Yjk3YyBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjhmOVx1Yzc3NCBBQkNcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWFjMWNcdWJiZjhcdWFjMDAgREVGXHVjMjFjXHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuIFx1YWRmOFx1YjdmYywgXHVjODgxXHVjNzQwIFx1YWUzOFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwYWNcdWM3NDQgXHViNTRjLCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IENCQURFRlx1YWMwMCBcdWI0MWNcdWIyZTQuIDFcdWNkMDhcdWFjMDAgXHVjOWMwXHViMGFjXHVjNzQ0IFx1YjU0Y1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNTVlXHVjNWQwIFx1YmMxOFx1YjMwMFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHVhYzFjXHViYmY4XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjMWNcdWJiZjhcdWIyOTQgQVx1YzY0MCBEXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIyOTQgQ0JEQUVGXHVhYzAwIFx1YjQxY1x1YjJlNC4gMlx1Y2QwOFx1YWMwMCBcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM3OTBcdWMyZTBcdWM3NTggXHVjNTVlXHVjNWQwIFx1YmMxOFx1YjMwMCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YWMxY1x1YmJmOFx1YjI5NCBCLEQsQSxFXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IENEQkVBRlx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlRcdWNkMDhcdWFjMDAgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFkZjhcdWI4ZjlcdWM3NTggXHVhYzFjXHViYmY4XHVjNzU4IFx1YzIxOCBOMVx1YWNmYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjhmOVx1Yzc1OCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjMjE4IE4yXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YjQ1MCBcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZGY4XHViOGY5XHVhY2ZjIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhZGY4XHViOGY5XHVjNzU4IFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVhYzFjXHViYmY4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YjQ1MCBcdWFkZjhcdWI4ZjlcdWM1ZDBcdWMxMWMgXHVjOTExXHViY2Y1XHViNDE4XHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0MCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgVCAmbGU7IDUwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRcdWNkMDhcdWFjMDAgXHVjOWMwXHViMDljIFx1ZDZjNFx1YzVkMCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWFjMWNcdWJiZjggXHVhZGY4XHViOGY5XHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YWRmOFx1YjhmOVx1Yzc0MCBcdWJjMThcdWIzMDAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3OFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS09MT05FIiwiZGVzY3JpcHRpb24iOiI8cD5XaGVuIG1vdmluZywgYW50cyBmb3JtIHJvd3Mgc28gdGhhdCBlYWNoIGFudCBleGNlcHQgdGhlIGZpcnN0IGlzIGJlaGluZCBhbm90aGVyIGFudC4gSXQgaXMgbm90IHdpZGVseSBrbm93biB3aGF0IGhhcHBlbnMgd2hlbiB0d28gcm93cyBvZiBhbnRzIG1vdmluZyBpbiBvcHBvc2l0ZSBkaXJlY3Rpb25zIHJ1biBpbnRvIGVhY2ggb3RoZXIgaW4gYSBwYXNzYWdlIHRvbyBuYXJyb3cgZm9yIGJvdGggcm93cyB0byBwYXNzIHRocm91Z2guIE9uZSB0aGVvcnkgc2F5cyB0aGF0LCBpbiB0aGF0IHNpdHVhdGlvbiwgYW50cyB3aWxsIGp1bXAgb3ZlciBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gcm9tIHRoZSBtb21lbnQgdGhlIHJvd3MgbWVldCwgZWFjaCBzZWNvbmQgZXZlcnkgYW50IGp1bXBzIG92ZXIgKG9yIGdldHMganVtcGVkIG92ZXIsIGFzIHRoZXkgYWdyZWUgdXBvbikgdGhlIGFudCBpbiBmcm9udCBvZiBoaW1zZWxmIHNvIHRoYXQgdGhlIHR3byBhbnRzIHN3YXAgcGxhY2VzLCBidXQgb25seSBpZiB0aGUgb3RoZXIgYW50IGlzIG1vdmluZyBpbiB0aGUgb3Bwb3NpdGUgZGlyZWN0aW9uLiBGaW5kIHRoZSBvcmRlciBvZiB0aGUgYW50cyBhZnRlciBUIHNlY29uZHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgTjEgYW5kIE4yLCB0aGUgbnVtYmVycyBvZiBhbnRzIGluIHRoZSBmaXJzdCBhbmQgc2Vjb25kIHJvd3MsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgdHdvIHJvd3MgY29udGFpbiB0aGUgb3JkZXJzIG9mIGFudHMgaW4gdGhlIGZpcnN0IGFuZCBzZWNvbmQgcm93IChmaXJzdCB0byBsYXN0KS4gRWFjaCBhbnQgaXMgdW5pcXVlbHkgZGV0ZXJtaW5lZCBieSBhbiB1cHBlcmNhc2UgbGV0dGVyIG9mIHRoZSBFbmdsaXNoIGFscGhhYmV0ICh0aGlzIGxldHRlciBpcyB1bmlxdWUgYmV0d2VlbiBib3RoIHJvd3MpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIFQgKDAgJmxlOyBUICZsZTsgNTApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgb3JkZXIgb2YgdGhlIGFudHMgYWZ0ZXIgVCBzZWNvbmRzIG9uIGEgc2luZ2xlIGxpbmUuIE91ciB2aWV3cG9pbnQgaXMgc3VjaCB0aGF0IHRoZSBmaXJzdCByb3cgb2YgYW50cyBjb21lcyBmcm9tIG91ciBsZWZ0IHNpZGUgYW5kIHRoZSBvdGhlciBvbmUgZnJvbSBvdXIgcmlnaHQgc2lkZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #2 3번