L Planet Amusement Park Visitor Arrangement

Problem Statement

The amusement park on planet L is very popular and attracts visitors from different planets. As the administrator of the park, Xiao Lan has access to the reservation system where all the visitor names are listed. Each visitor name follows the pattern: it starts with an uppercase English letter followed by zero or more lowercase English letters. Note that visitors may share the same name.

In order to manage the park effectively, visitors must book a time slot in advance. Xiao Lan loves things in increasing order. Today, he has decided to split all the reservations into two groups: the visitors who will enjoy the park in the morning and the rest in the afternoon. The visitors scheduled for the morning must appear in the same order as they were originally reserved, and their names must form a strictly increasing sequence.

The comparison rule for two names A and B is defined as follows: There exists an integer i such that the first i letters of A and B are identical, and the (i+1)-th letter of A is less than the (i+1)-th letter of B. In particular, if A is a prefix of B (i.e. A ends and B has an extra letter), then A is considered smaller than B.

Your task is to choose a subset of the visitors (preserving their original order) to play in the morning such that:

1. The number of visitors in the morning is maximized.
2. If there are multiple solutions with the maximum number of visitors, choose the one in which the resulting morning list (when compared element by element) is lexicographically smallest.

For example, if the booking order is:

A
C
B
D
E

There are two increasing sequences of maximum length 4: [A, C, D, E] and [A, B, D, E]. Since [A, B, D, E] is lexicographically smaller (because B < C), it should be chosen.

inputFormat

Input Format

The first line contains an integer n (n ≥ 1), the number of visitors who reserved the park.

Then follow n lines, each containing a visitor name. Each name is a non-empty string that starts with an uppercase English letter followed by zero or more lowercase English letters.

outputFormat

Output Format

Output the names of the visitors chosen for the morning, each on a separate line, in the same order as in the input. This sequence should be a maximum-length strictly increasing (lexicographically) subsequence, and among such sequences, the lexicographically smallest one.

sample

5
A
B
C
D
E

A
B
C
D
E

</p>