The Canadian Federal Election is soon, and it may be time to understand how Canadian Pariliament works! All you need to know is that the party with the most amount of seats forms the government, while the party with the second most seats forms the official opposition. There are ~N~ parties in the election. You would like to know who won the election, and who is the leader of the opposition.

Constraints

~2 \leq N,|S_i| \leq 100~

~1 \leq A \leq 10^4~

Input Specification

The first line will contain an integer ~N~.

For the next ~N~ lines, the ~i~th line will contain a string ~S_i~, the name of the party, and ~A_i~, the number of seats that party received.

It is guaranteed that the string will only contain alphanumeric characters and no spaces.

Ouput Specification

Output two lines. The first line will contain the party that won the election, followed by the word government.

The second line will contain the party that was in second place, followed by the words official opposition.

It is guaranteed there is a distinct winner and a distinct official opposition.

Sample Input

5
Liberals 188
Conservatives 123
Bloc 22
NDP 9
Green 1

Sample Output

Liberals government
Conservatives official opposition