4.3 Sibling String

Score: 100pts

Time Limit: 1.00 sec

You are given an integer n which represents the number of chars, on the next n lines, you will be given a char and its count.

You need to construct a string with the chars and their count in the given order.

Output the next smallest colexicographic string.

Assume the strings are in a dictionary.

You need to construct a string with the chars and their count in the given order.

Output the next smallest colexicographic string.

Assume the strings are in a dictionary.

Constraints

\(1 \leq n \leq 100\)

\(1 \leq count \leq 1000\)

Only lowercase characters

\(1 \leq count \leq 1000\)

Only lowercase characters

Input Format

The first line contains the number of characters \(n\)

The next \(n\) lines contain the character and its count

The next \(n\) lines contain the character and its count

Output Format

Output a string which is the smallest colexicographic string

Example 1

Input:

1

z 1

Output:

aa

Explanation:

Since the strings are assumed to be in a dictionary, after 'z', 'aa' comes which is the next smallest colexicographic string.

1

z 1

Output:

aa

Explanation:

Since the strings are assumed to be in a dictionary, after 'z', 'aa' comes which is the next smallest colexicographic string.