시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 76 44 20 52.632%

문제

상근이는 두 과일의 유전자를 합쳐, 새로운 과일을 만드는 작업을 하고 있다. 두 과일을 합치는 작업은 매우 어렵다. 만약, 성공을 하게 된다면 새로운 과일의 맛은 두 과일을 동시에 먹는 맛과 같을 것이다.

사실 상근이는 이 작업을 시작하기 전에, 새로운 과일의 이름을 짓고 작업을 시작 한다. 물론, 사과(apple)와 배(pear)를 합친 과일을 apple-pear라고 불러도 되지만, 이 이름은 관심을 끌기에 적절하지 않는다.

상근이는 두 과일의 이름을 부분 문자열로 포함하는 문자열 중, 가장 길이가 짧은 것을 새로운 과일의 이름으로 사용하려고 한다. 예를 들어, applear는 apple과 pear를 모두 포함한다. (APPLEar, apPlEAR) 또, 이 이름이 길이도 가장 짧다. 크랜베리(cranberry)와 보이즌베리(boysenberry)를 합친 이름은 boysecranberry나 craboysenberry가 될 것이다.

두 과일의 이름이 주어졌을 때, 두 과일을 합친 새로운 과일의 이름을 구하는 프로그램을 작성하시오. 이때, 문제에 주어진 조건을 만족해야 한다.

입력

입력을 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 합치려고 하는 두 과일의 이름으로 이루어져 있다. 과일의 이름은 알파벳으로 이루어졌으며, 길이는 최대 100이다.

출력

각 테스트 케이스에 대해서, 가장 짧은 새로운 과일의 이름을 출력한다. 만약, 가능한 이름이 여러 가지라면, 아무거나 출력한다.

예제 입력 1

apple peach
ananas banana
pear peach

예제 출력 1

appleach
bananas
pearch
W3sicHJvYmxlbV9pZCI6IjY1NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzhcdWI4NWNcdWM2YjQgXHVhY2ZjXHVjNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViNDUwIFx1YWNmY1x1Yzc3Y1x1Yzc1OCBcdWM3MjBcdWM4MDRcdWM3OTBcdWI5N2MgXHVkNTY5XHVjY2QwLCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhY2ZjXHVjNzdjXHVjNzQ0IFx1YjljY1x1YjRkY1x1YjI5NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViNDUwIFx1YWNmY1x1Yzc3Y1x1Yzc0NCBcdWQ1NjlcdWNlNThcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzQwIFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MzVcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjMTMxXHVhY2Y1XHVjNzQ0IFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTRcdWJhNzQgXHVjMGM4XHViODVjXHVjNmI0IFx1YWNmY1x1Yzc3Y1x1Yzc1OCBcdWI5ZGJcdWM3NDAgXHViNDUwIFx1YWNmY1x1Yzc3Y1x1Yzc0NCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHViYTM5XHViMjk0IFx1YjlkYlx1YWNmYyBcdWFjMTlcdWM3NDQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYWNcdWMyZTQgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHVhZTMwIFx1YzgwNFx1YzVkMCwgXHVjMGM4XHViODVjXHVjNmI0IFx1YWNmY1x1Yzc3Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDQgXHVjOWQzXHVhY2UwIFx1Yzc5MVx1YzVjNVx1Yzc0NCBcdWMyZGNcdWM3OTEgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWI4NjAsIFx1YzBhY1x1YWNmYyhhcHBsZSlcdWM2NDAgXHViYzMwKHBlYXIpXHViOTdjIFx1ZDU2OVx1Y2U1YyBcdWFjZmNcdWM3N2NcdWM3NDQgYXBwbGUtcGVhclx1Yjc3Y1x1YWNlMCBcdWJkODhcdWI3ZWNcdWIzYzQgXHViNDE4XHVjOWMwXHViOWNjLCBcdWM3NzQgXHVjNzc0XHViOTg0XHVjNzQwIFx1YWQwMFx1YzJlY1x1Yzc0NCBcdWIwNGNcdWFlMzBcdWM1ZDAgXHVjODAxXHVjODA4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjQ1MCBcdWFjZmNcdWM3N2NcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQ0IFx1YmQ4MFx1YmQ4NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBcdWM5MTEsIFx1YWMwMFx1YzdhNSBcdWFlMzhcdWM3NzRcdWFjMDAgXHVjOWU3XHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVhY2ZjXHVjNzdjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBhcHBsZWFyXHViMjk0IGFwcGxlXHVhY2ZjIHBlYXJcdWI5N2MgXHViYWE4XHViNDUwIFx1ZDNlY1x1ZDU2OFx1ZDU1Y1x1YjJlNC4gKEFQUExFYXIsIGFwUGxFQVIpIFx1YjYxMCwgXHVjNzc0IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWFlMzhcdWM3NzRcdWIzYzQgXHVhYzAwXHVjN2E1IFx1YzllN1x1YjJlNC4gXHVkMDZjXHViNzljXHViY2EwXHViOWFjKGNyYW5iZXJyeSlcdWM2NDAgXHViY2Y0XHVjNzc0XHVjOThjXHViY2EwXHViOWFjKGJveXNlbmJlcnJ5KVx1Yjk3YyBcdWQ1NjlcdWNlNWMgXHVjNzc0XHViOTg0XHVjNzQwIGJveXNlY3JhbmJlcnJ5XHViMDk4IGNyYWJveXNlbmJlcnJ5XHVhYzAwIFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWFjZmNcdWM3N2NcdWM3NTggXHVjNzc0XHViOTg0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWFjZmNcdWM3N2NcdWM3NDQgXHVkNTY5XHVjZTVjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWFjZmNcdWM3N2NcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM3NzRcdWI1NGMsIFx1YmIzOFx1YzgxY1x1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDQgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU2OVx1Y2U1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWIyOTQgXHViNDUwIFx1YWNmY1x1Yzc3Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhY2ZjXHVjNzdjXHVjNzU4IFx1Yzc3NFx1Yjk4NFx1Yzc0MCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODRjXHVjNzNjXHViYTcwLCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWM5ZTdcdWM3NDAgXHVjMGM4XHViODVjXHVjNmI0IFx1YWNmY1x1Yzc3Y1x1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCwgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI2NTc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQWR2YW5jZWQgRnJ1aXRzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY29tcGFueSAmcXVvdDsyMXN0IENlbnR1cnkgRnJ1aXRzJnF1b3Q7IGhhcyBzcGVjaWFsaXplZCBpbiBjcmVhdGluZyBuZXcgc29ydHMgb2YgZnJ1aXRzIGJ5IHRyYW5zZmVycmluZyBnZW5lcyBmcm9tIG9uZSBmcnVpdCBpbnRvIHRoZSBnZW5vbWUgb2YgYW5vdGhlciBvbmUuIE1vc3QgdGltZXMgdGhpcyBtZXRob2QgZG9lc24mIzM5O3Qgd29yaywgYnV0IHNvbWV0aW1lcywgaW4gdmVyeSByYXJlIGNhc2VzLCBhIG5ldyBmcnVpdCBlbWVyZ2VzIHRoYXQgdGFzdGVzIGxpa2UgYSBtaXh0dXJlIGJldHdlZW4gYm90aCBvZiB0aGVtLjxcL3A+XHJcblxyXG48cD5BIGJpZyB0b3BpYyBvZiBkaXNjdXNzaW9uIGluc2lkZSB0aGUgY29tcGFueSBpcyAmcXVvdDtIb3cgc2hvdWxkIHRoZSBuZXcgY3JlYXRpb25zIGJlIGNhbGxlZD8mcXVvdDsgQSBtaXh0dXJlIGJldHdlZW4gYW4gYXBwbGUgYW5kIGEgcGVhciBjb3VsZCBiZSBjYWxsZWQgYW4gYXBwbGUtcGVhciwgb2YgY291cnNlLCBidXQgdGhpcyBkb2VzbiYjMzk7dCBzb3VuZCB2ZXJ5IGludGVyZXN0aW5nLiBUaGUgYm9zcyBmaW5hbGx5IGRlY2lkZXMgdG8gdXNlIHRoZSBzaG9ydGVzdCBzdHJpbmcgdGhhdCBjb250YWlucyBib3RoIG5hbWVzIG9mIHRoZSBvcmlnaW5hbCBmcnVpdHMgYXMgc3ViLXN0cmluZ3MgYXMgdGhlIG5ldyBuYW1lLiBGb3IgaW5zdGFuY2UsICZxdW90O2FwcGxlYXImcXVvdDsgY29udGFpbnMgJnF1b3Q7YXBwbGUmcXVvdDsgYW5kICZxdW90O3BlYXImcXVvdDsgKEFQUExFYXIgYW5kIGFwUGxFQVIpLCBhbmQgdGhlcmUgaXMgbm8gc2hvcnRlciBzdHJpbmcgdGhhdCBoYXMgdGhlIHNhbWUgcHJvcGVydHkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgY29tYmluYXRpb24gb2YgYSBjcmFuYmVycnkgYW5kIGEgYm95c2VuYmVycnkgd291bGQgdGhlcmVmb3JlIGJlIGNhbGxlZCBhICZxdW90O2JveXNlY3JhbmJlcnJ5JnF1b3Q7IG9yIGEgJnF1b3Q7Y3JhYm95c2VuYmVycnkmcXVvdDssIGZvciBleGFtcGxlLjxcL3A+XHJcblxyXG48cD5Zb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjb21wdXRlcyBzdWNoIGEgc2hvcnRlc3QgbmFtZSBmb3IgYSBjb21iaW5hdGlvbiBvZiB0d28gZ2l2ZW4gZnJ1aXRzLiBZb3VyIGFsZ29yaXRobSBzaG91bGQgYmUgZWZmaWNpZW50LCBvdGhlcndpc2UgaXQgaXMgdW5saWtlbHkgdGhhdCBpdCB3aWxsIGV4ZWN1dGUgaW4gdGhlIGFsbG90ZWQgdGltZSBmb3IgbG9uZyBmcnVpdCBuYW1lcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggbGluZSBvZiB0aGUgaW5wdXQgZmlsZSBjb250YWlucyB0d28gc3RyaW5ncyB0aGF0IHJlcHJlc2VudCB0aGUgbmFtZXMgb2YgdGhlIGZydWl0cyB0aGF0IHNob3VsZCBiZSBjb21iaW5lZC4gQWxsIG5hbWVzIGhhdmUgYSBtYXhpbXVtIGxlbmd0aCBvZiAxMDAgYW5kIG9ubHkgY29uc2lzdCBvZiBhbHBoYWJldGljIGNoYXJhY3RlcnMuPFwvcD5cclxuXHJcbjxwPklucHV0IGlzIHRlcm1pbmF0ZWQgYnkgZW5kIG9mIGZpbGU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgc2hvcnRlc3QgbmFtZSBvZiB0aGUgcmVzdWx0aW5nIGZydWl0IG9uIG9uZSBsaW5lLiBJZiBtb3JlIHRoYW4gb25lIHNob3J0ZXN0IG5hbWUgaXMgcG9zc2libGUsIGFueSBvbmUgaXMgYWNjZXB0YWJsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=