1639 - Freedom of Choice

Created by Timus Top Coders: Third Challenge - Ilya Grebnov & Nikita Rybak & Dmitry Kovalioff
Added by ymondelo20 (2011-11-26)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 62 MB | Output: 64 MB | Size: 29 KB
Enabled languages
Available in

Description

According to democratic traditions, both candidates entertain with digging dirt upon each other to the cheers of their voters' approval. When occasion offers, each candidate makes an election speech, which is devoted to blaming his opponent for corruption, disrespect for the elders and terrorism affiliation. As a result the speeches of Mohammed and Ahmed have become nearly the same, and now it does not matter for the voters for whom to vote.

The third candidate, a chairman of Albanian socialist party comrade Ktulhu wants to make use of this situation. He has been lazy to write his own election speech, but noticed, that some fragments of the speeches of Mr. Tahir-ogly and Mr. Kasym-bey are completely identical. Then Mr. Ktulhu decided to take the longest identical fragment and use it as his election speech.
;jsessionid=AFF3AB51840F70BF433DDDB578C0C419
According to democratic traditions, both candidates entertain with digging dirt upon each other to the cheers of their voters' approval. When occasion offers, each candidate makes an election speech, which is devoted to blaming his opponent for corruption, disrespect for the elders and terrorism affiliation. As a result the speeches of Mohammed and Ahmed have become nearly the same, and now it does not matter for the voters for whom to vote.

The third candidate, a chairman of Albanian socialist party comrade Ktulhu wants to make use of this situation. He has been lazy to write his own election speech, but noticed, that some fragments of the speeches of Mr. Tahir-ogly and Mr. Kasym-bey are completely identical. Then Mr. Ktulhu decided to take the longest identical fragment and use it as his election speech.
;jsessionid=AFF3AB51840F70BF433DDDB578C0C419
According to democratic traditions, both candidates entertain with digging dirt upon each other to the cheers of their voters' approval. When occasion offers, each candidate makes an election speech, which is devoted to blaming his opponent for corruption, disrespect for the elders and terrorism affiliation. As a result the speeches of Mohammed and Ahmed have become nearly the same, and now it does not matter for the voters for whom to vote.

The third candidate, a chairman of Albanian socialist party comrade Ktulhu wants to make use of this situation. He has been lazy to write his own election speech, but noticed, that some fragments of the speeches of Mr. Tahir-ogly and Mr. Kasym-bey are completely identical. Then Mr. Ktulhu decided to take the longest identical fragment and use it as his election speech.
;jsessionid=AFF3AB51840F70BF433DDDB578C0C419

Input specification

The first line contains the integer number N (1 <= N <= 10^5). The second line contains the speech of Mr. Tahir-ogly. The third line contains the speech of Mr. Kasym-bey. Each speech consists of N capital latin letters.;jsessionid=AFF3AB51840F70BF433DDDB578C0C419
The first line contains the integer number N (1 <= N <= 10^5). The second line contains the speech of Mr. Tahir-ogly. The third line contains the speech of Mr. Kasym-bey. Each speech consists of N capital latin letters.;jsessionid=AFF3AB51840F70BF433DDDB578C0C419
The first line contains the integer number N (1 <= N <= 10^5). The second line contains the speech of Mr. Tahir-ogly. The third line contains the speech of Mr. Kasym-bey. Each speech consists of N capital latin letters.;jsessionid=AFF3AB51840F70BF433DDDB578C0C419

Output specification

You should output the speech of Mr. Ktulhu. If the problem has several solutions, you should output the lexicographically smallest of them.
You should output the speech of Mr. Ktulhu. If the problem has several solutions, you should output the lexicographically smallest of them.
The first line contains the integer number N (1 <= N <= 10^5). The second line contains the speech of Mr. Tahir-ogly. The third line contains the speech of Mr. Kasym-bey. Each speech consists of N capital latin letters.;jsessionid=AFF3AB51840F70BF433DDDB578C0C419

Sample input

28
VOTEFORTHEGREATALBANIAFORYOU
CHOOSETHEGREATALBANIANFUTURE

Sample output

THEGREATALBANIA

Hint(s)