Substrings
You are given K strings S1, S2, ..., SK. Sum of their lengths does not exceed 1 000 000 characters and they can only contain small letters of English alphabet.
Your task is to find, for each string, its shortest substring which is not substring of any other of the given strings.
InputIn the first line of the input, there is a natural number K ( 2 \leq K \leq 10 000 ), the number of strings.
In each of the next K rows there is a string.
In each of the next K rows there is a string.
OutputIn K rows, output for each string (in the order they were given in the input) its substring as explained above.
If there is more than one such substring, output the leftmost of them (the closest one to the beginning of the word).
If such a substring does not exist, output "nopeZ" instead.
If there is more than one such substring, output the leftmost of them (the closest one to the beginning of the word).
If such a substring does not exist, output "nopeZ" instead.
Input
Output
2
abab
acbcOutput
ab
cInput
Output
2
abab
ababaOutput
nopeZ
babaSubmit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.