시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1046 448 376 47.716%

문제

팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다.

상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC 문제가 저장되어 있는 서버에 접속할 수 있는 비밀번호에 대한 힌트이다. 비밀번호는 k개의 단어 중에서 두 단어를 합쳐야 되고, 팰린드롬이어야 한다. 예를 들어, 단어가 aaba, ba, ababa, bbaa, baaba일 때, ababa와 ba를 합치면 팰린드롬 abababa를 찾을 수 있다.

단어 k개 주어졌을 때, 팰린드롬을 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 공책에 적혀져있는 단어의 수 k(1 ≤ k ≤ 100)가 주어진다. 다음 k개 줄에는 a부터 z까지 알파벳으로 이루어진 단어가 한 줄에 하나씩 주어진다. 모든 단어 길이의 합은 10,000보다 작거나 같다.

출력

각 테스트 케이스마다 팰린드롬을 출력한다. 만약, 가능한 팰린드롬이 여러 가지라면 아무거나 출력한다. 팰린드롬을 만들 수 없는 경우에는 0을 출력한다.

예제 입력 1

2
5
aaba
ba
ababa
bbaa
baaba
3
abc
bcd
cde

예제 출력 1

abababa
0
W3sicHJvYmxlbV9pZCI6Ijg4OTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0MCBcdWM1YjRcdWIyOTAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1Yzc3ZFx1YzViNFx1YjNjNCBcdWQ1NmRcdWMwYzEgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWM3N2RcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIGNpdmljLCByYWRhciwgcm90b3IsIG1hZGFtXHVjNzQwIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjJlOFx1YzViNCBrXHVhYzFjIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWNjNDVcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWFjZjVcdWNjNDVcdWM3NTggXHViMmU4XHVjNWI0XHViMjk0IElDUEMgXHViYjM4XHVjODFjXHVhYzAwIFx1YzgwMFx1YzdhNVx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViYzg0XHVjNWQwIFx1YzgxMVx1YzE4ZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmU0NFx1YmMwMFx1YmM4OFx1ZDYzOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVkNzhjXHVkMmI4XHVjNzc0XHViMmU0LiBcdWJlNDRcdWJjMDBcdWJjODhcdWQ2MzhcdWIyOTQga1x1YWMxY1x1Yzc1OCBcdWIyZThcdWM1YjQgXHVjOTExXHVjNWQwXHVjMTFjIFx1YjQ1MCBcdWIyZThcdWM1YjRcdWI5N2MgXHVkNTY5XHVjY2QwXHVjNTdjIFx1YjQxOFx1YWNlMCwgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViMmU4XHVjNWI0XHVhYzAwIGFhYmEsIGJhLCBhYmFiYSwgYmJhYSwgYmFhYmFcdWM3N2MgXHViNTRjLCBhYmFiYVx1YzY0MCBiYVx1Yjk3YyBcdWQ1NjlcdWNlNThcdWJhNzQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjIGFiYWJhYmFcdWI5N2MgXHVjYzNlXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YzViNCBrXHVhYzFjIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0NCBcdWNjM2VcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVjYzQ1XHVjNWQwIFx1YzgwMVx1ZDYwMFx1YzgzOFx1Yzc4OFx1YjI5NCBcdWIyZThcdWM1YjRcdWM3NTggXHVjMjE4IGsoMSAmbGU7IGsgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIGtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IGFcdWJkODBcdWQxMzAgelx1YWU0Y1x1YzljMCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWIyZThcdWM1YjQgXHVhZTM4XHVjNzc0XHVjNzU4IFx1ZDU2OVx1Yzc0MCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg4OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQYWxpbmRyb21lIiwiZGVzY3JpcHRpb24iOiI8cD5BIHBhbGluZHJvbWUgaXMgYSB3b3JkIHdoaWNoIGNhbiBiZSByZWFkIHRoZSBzYW1lIHdheSBpbiBlaXRoZXIgZGlyZWN0aW9uLiBGb3IgZXhhbXBsZSwgdGhlIGZvbGxvd2luZyB3b3JkcyBhcmUgcGFsaW5kcm9tZXM6IGNpdmljLCByYWRhciwgcm90b3IsIGFuZCBtYWRhbS4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuWW91IGhhdmUgZm91bmQgYSBub3RlIHRoYXQgY29udGFpbnMgayB3b3Jkcy4gTGF0ZXIgeW91IGZvdW5kIG91dCB0aGF0IHRoZSBub3RlIGNvbnRhaW5zIGEgY2x1ZSB0byB0aGUgcGFzc3dvcmQgZm9yIGFjY2Vzc2luZyB0aGUgbW9zdCBzZWNyZXQgc2VydmVyIHdoZXJlIElDUEMgcHJvYmxlbXMgYXJlIHN0b3JlZC4gVW5mb3J0dW5hdGVseSwgdGhlIHBhc3N3b3JkIGlzIG5vdCB3cml0dGVuIGFzIGl0IGlzLiBJdCBpcyB0aGUgY29uY2F0ZW5hdGlvbiBvZiB0d28gZGlmZmVyZW50IHN0cmluZ3Mgb3V0IG9mIHRoZSBrIHdvcmRzLCBhbmQgaXQgaXMgYSBwYWxpbmRyb21lLiBGb3IgZXhhbXBsZSwgeW91IGNhbiBmaW5kIHRoZSBwYWxpbmRyb21lIGFiYWJhYmEgZnJvbSB0aGUgZml2ZSB3b3JkcyBhYWJhLCBiYSwgYWJhYmEsIGJiYWEsIGFuZCBiYWFiYSBieSBjb25jYXRlbmF0aW5nIGFiYWJhIGFuZCBiYS4mbmJzcDs8YnIgXC8+XHJcbiZuYnNwOzxiciBcLz5cclxuV3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIHBhc3N3b3JkIGZyb20gayBnaXZlbiB3b3Jkcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byByZWFkIGZyb20gc3RhbmRhcmQgaW5wdXQuIFRoZSBpbnB1dCBjb25zaXN0cyBvZiBUIHRlc3QgY2FzZXMuIFRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcyBUIGlzIGdpdmVuIGluIHRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgb25lIGludGVnZXIgayAoMSAmbGU7IGsgJmxlOyAxMDApLCB3aGVyZSBrIGlzIHRoZSBudW1iZXIgb2Ygd29yZHMgaW4gdGhlIG5vdGUuIEluIHRoZSBuZXh0IGsgbGluZXMgb2YgZWFjaCB0ZXN0IGNhc2UsIGVhY2ggbGluZSBjb250YWlucyBhIHdvcmQgaW4gQVNDSUkgY2hhcmFjdGVycyBiZXR3ZWVuIGEgYW5kIHouIFRoZSBzdW0gb2YgbGVuZ3RocyBvZiBzdHJpbmdzIGZvciBlYWNoIGNhc2UgaXMgZXF1YWwgdG8gb3Igc21hbGxlciB0aGFuIDEwLDAwMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBGb3IgZWFjaCB0ZXN0IGNhc2UsIGlmIHRoZXJlIGlzIG5vIHBhbGluZHJvbWUgb2J0YWluZWQgYnkgY29uY2F0ZW5hdGluZyB0d28gc3RyaW5ncywgcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIDAuIE90aGVyd2lzZSwgcHJpbnQgdGhlIHBhbGluZHJvbWUuIElmIHRoZXJlIGFyZSB0d28gb3IgbW9yZSBwYWxpbmRyb21lcywganVzdCBwcmludCBvbmUgb2YgdGhlbS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2012 E번