시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB87524417327.903%

문제

희현이는 원장선생님 말씀에 토를 다는 것을 몹시 좋아한다. 토를 단다는 것은 원장선생님께서 어떤 단어를 말씀하시면 그 단어의 맨 앞이나 중간, 혹은 맨 뒤에 한 글자를 끼워 넣어서 새로운 단어를 만드는 것으로, 버릇없는 행동과는 아무런 관계가 없는 순수한 단어 놀이이다.

희현이는 사전에 등재된 단어만을 사용한다. 사전은 d개의 단어로 구성되어 있으며, 각 단어는 80자 이내의 알파벳 소문자로만 이루어져 있다. 희현이는 원장선생님께서 어떤 단어를 말씀하셨을 때, 한 글자씩 토를 달아 사전에 등재된 단어를 계속 만들어 갈 경우, 가장 긴 단어를 만들려면 어떻게 해야 하는지가 궁금해졌다. 이를 해결하는 프로그램을 작성하라.

입력

첫 줄에 사전에 등재된 단어의 수 d와, 원장님이 처음 말씀하신 단어가 주어진다. (1 ≤ d ≤ 1,000) 원장님이 처음 말씀하신 단어의 길이는 세 글자이며, 사전에 있는 단어를 말씀하셨다. 다음 d개의 줄에는 사전에 등재된 단어가 한 줄에 하나씩 주어진다.

출력

첫 줄에 토달기 규칙을 지키며 단어를 만들어 갈 때, 만들 수 있는 단어 중 가장 긴 것을 출력한다. 답이 여럿일 경우 어느 것이나 상관없다.

예제 입력 1

9 cal
cal
calf
calfs
call
calls
choral
chorale
coal
coral

예제 출력 1

chorale

힌트

cal, coal, coral, choral, chorale 순으로 단어를 만들어 나가면 된다.

W3sicHJvYmxlbV9pZCI6IjE4OTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxYTBcdWIyZWNcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDc2Y1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDggXHViOWQwXHVjNTAwXHVjNWQwIFx1ZDFhMFx1Yjk3YyBcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmFiOVx1YzJkYyBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuIFx1ZDFhMFx1Yjk3YyBcdWIyZThcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQwIFx1YzZkMFx1YzdhNVx1YzEyMFx1YzBkZFx1YjJkOFx1YWVkOFx1YzExYyBcdWM1YjRcdWI1YTQgXHViMmU4XHVjNWI0XHViOTdjIFx1YjlkMFx1YzUwMFx1ZDU1OFx1YzJkY1x1YmE3NCBcdWFkZjggXHViMmU4XHVjNWI0XHVjNzU4IFx1YjllOCBcdWM1NWVcdWM3NzRcdWIwOTggXHVjOTExXHVhYzA0LCBcdWQ2MzlcdWM3NDAgXHViOWU4IFx1YjRhNFx1YzVkMCBcdWQ1NWMgXHVhZTAwXHVjNzkwXHViOTdjIFx1YjA3Y1x1YzZjYyBcdWIxMjNcdWM1YjRcdWMxMWMgXHVjMGM4XHViODVjXHVjNmI0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVhYzgzXHVjNzNjXHViODVjLCBcdWJjODRcdWI5ODdcdWM1YzZcdWIyOTQgXHVkNTg5XHViM2Q5XHVhY2ZjXHViMjk0IFx1YzU0NFx1YmIzNFx1YjdmMCBcdWFkMDBcdWFjYzRcdWFjMDAgXHVjNWM2XHViMjk0IFx1YzIxY1x1YzIxOFx1ZDU1YyBcdWIyZThcdWM1YjQgXHViMTgwXHVjNzc0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ3NmNcdWQ2MDRcdWM3NzRcdWIyOTQmbmJzcDtcdWMwYWNcdWM4MDRcdWM1ZDAgXHViNGYxXHVjN2FjXHViNDFjIFx1YjJlOFx1YzViNFx1YjljY1x1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YzBhY1x1YzgwNFx1Yzc0MCBkXHVhYzFjXHVjNzU4IFx1YjJlOFx1YzViNFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWFjMDEgXHViMmU4XHVjNWI0XHViMjk0IDgwXHVjNzkwIFx1Yzc3NFx1YjBiNFx1Yzc1OCBcdWM1NGNcdWQzMGNcdWJjYjMgXHVjMThjXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDc2Y1x1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM2ZDBcdWM3YTVcdWMxMjBcdWMwZGRcdWIyZDhcdWFlZDhcdWMxMWMgXHVjNWI0XHViNWE0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5ZDBcdWM1MDBcdWQ1NThcdWMxNjhcdWM3NDQgXHViNTRjLCBcdWQ1NWMgXHVhZTAwXHVjNzkwXHVjNTI5IFx1ZDFhMFx1Yjk3YyBcdWIyZWNcdWM1NDQgXHVjMGFjXHVjODA0XHVjNWQwIFx1YjRmMVx1YzdhY1x1YjQxYyBcdWIyZThcdWM1YjRcdWI5N2MgXHVhY2M0XHVjMThkIFx1YjljY1x1YjRlNFx1YzViNCBcdWFjMDggXHVhY2JkXHVjNmIwLCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWJhNzQgXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzBcdWFjMDAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LiBcdWM3NzRcdWI5N2MgXHVkNTc0XHVhY2IwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWI0ZjFcdWM3YWNcdWI0MWMgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOCBkXHVjNjQwLCBcdWM2ZDBcdWM3YTVcdWIyZDhcdWM3NzQgXHVjYzk4XHVjNzRjIFx1YjlkMFx1YzUwMFx1ZDU1OFx1YzJlMCBcdWIyZThcdWM1YjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZuYnNwOyZsZTsgZCAmbGU7IDEsMDAwKSBcdWM2ZDBcdWM3YTVcdWIyZDhcdWM3NzQgXHVjYzk4XHVjNzRjIFx1YjlkMFx1YzUwMFx1ZDU1OFx1YzJlMCBcdWIyZThcdWM1YjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YzEzOCBcdWFlMDBcdWM3OTBcdWM3NzRcdWJhNzAsIFx1YzBhY1x1YzgwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0XHViOTdjIFx1YjlkMFx1YzUwMFx1ZDU1OFx1YzE2OFx1YjJlNC4gXHViMmU0XHVjNzRjIGRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBhY1x1YzgwNFx1YzVkMCBcdWI0ZjFcdWM3YWNcdWI0MWMgXHViMmU4XHVjNWI0XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDFhMFx1YjJlY1x1YWUzMCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViYTcwIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHVhYzA4IFx1YjU0YywgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViMmU4XHVjNWI0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YWM4M1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZmZcdWM3N2MgXHVhY2JkXHVjNmIwIFx1YzViNFx1YjI5MCBcdWFjODNcdWM3NzRcdWIwOTggXHVjMGMxXHVhZDAwXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5jYWwsIGNvYWwsIGNvcmFsLCBjaG9yYWwsIGNob3JhbGUgXHVjMjFjXHVjNzNjXHViODVjIFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHViMDk4XHVhYzAwXHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE4OTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUcmF2ZWwgR2FtZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBjb3dzIGFyZSB0YWtpbmcgYSB0cmlwIHRvIHRoZSBsYWtlcyBpbiBNaW5uZXNvdGEuIExpa2UgZXZlcnlvbmUgZWxzZSwgdGhleSBhcmUgYm9yZWQgYW5kIGFyZSBwbGF5aW5nICZxdW90O3RyYXZlbCBnYW1lcyZxdW90OyB0byBwYXNzIHRoZSB0aW1lIGF3YXkuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgdHJhdmVsIGdhbWUsIHRoZSBmaXJzdCBjb3cgdGhpbmtzIG9mIGEgdGhyZWUgbGV0dGVyIHdvcmQgZnJvbSB0aGUgU2FjcmVkIFRyYXZlbCBHYW1lIERpY3Rpb25hcnkgKFNUR0QpLiBUaGUgbmV4dCBjb3cgaW4gbGluZSBtdXN0IGFkZCBhIGxldHRlciB0byB0aGUgd29yZCAoYXQgdGhlIGJlZ2lubmluZywgYmV0d2VlbiB0d28gbGV0dGVycywgb3IgYXQgdGhlIGVuZCkgdG8gbWFrZSBhbm90aGVyIHdvcmQgaW4gdGhlIFNUR0QuIFRoZSBjb3dzIGFyZSBjdXJpb3VzIGFzIHRvIGp1c3QgaG93IGJpZyB0aGUgZmluYWwgd29yZCBjYW4gYmUuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgZGljdGlvbmFyeSBvZiBEICgxICZsdDs9IEQgJmx0Oz0gMTAwMCkgd29yZHMgYW5kIGEgc3RhcnRpbmcgd29yZCwgZmluZCBhbnkgb2YgdGhlIGxvbmdlc3QgcG9zc2libGUgd29yZHMgdGhhdCBjYW4gYmUgZm9ybWVkIHBsYXlpbmcgdGhpcyB0cmF2ZWwgZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgaW50ZWdlciBEIGZvbGxvd2VkIGJ5IGEgc3BhY2UgZm9sbG93ZWQgYnkgYSBsZWdhbCB0aHJlZSBsZXR0ZXIgd29yZC48XC9saT5cclxuXHQ8bGk+TGluZSAyIHRocm91Z2ggRCsxOiBFYWNoIGxpbmUgY29udGFpbnMgYSBsZWdhbCB3b3JkIG5vIGxvbmdlciB0aGFuIDgwIGNoYXJhY3RlcnMsIGNvbnNpc3Rpbmcgb25seSBvZiBsb3dlcmNhc2UgbGV0dGVycywgZnJvbSB0aGUgU1RHRC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCB0aGUgbG9uZ2VzdCB3b3JkIHRoYXQgY2FuIGJlIGZvcm1lZCBieSBleHRlbmRpbmcgdGhlIGlucHV0IHNlZWQuPFwvcD5cclxuIiwiaGludCI6IjxwPkZyb20gdGhlIHNlcXVlbmNlOiBjYWwsIGNvYWwsIGNvcmFsLCBjaG9yYWwsIGNob3JhbGU8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=