Word Pair Suggestion

Given a set of sentences, your task is to determine for each word the most frequent word that immediately follows it. In case of a tie in frequency, choose the one that is lexicographically smallest.

For a given word \(w\) and a candidate next word \(v\), the frequency is defined as the number of times the pair \( (w, v) \) occurs in the sentences.

inputFormat

The first line contains an integer (N) representing the number of sentences. Each of the following (N) lines contains a sentence composed of space-separated words.

outputFormat

Output each suggestion pair in a separate line in the format 'word next_word', sorted in lexicographical order by the word. If a word does not have any following word, simply output the word.## sample

3
hello world this is a test
this is a test case
test case scenario

a test
case scenario
hello world
is a
test case
this is
world this