Lingvista

Mister S likes words, so he has invented his own language, which consists of N words. He wants to enrich the language by adding new words, where each word is obtained by appending or prepending letters to some of the already existing words.

Mister S has already come up with M new words. In order to test whether the words satisfy the (ap/pre)pending rule, he asks you to tell him for a given word w what is the longest word in his language which results in w by appending letters, and what is the longest word in his language which results in w by prepending letters.
If such a word does not exist in his languages, you should print "ne postoji" (without quotes).

Constraints:
1 <= N,M <= 1000
In 80% of the test cases each word will contain at most 50 letters, while in the remaining 20% of the test cases each word will contain at most 1000 letters.