Problem Description

The amusement park on Planet $\mathrm{L}$ is very interesting and attracts tourists from many planets. Xiao Lan is the administrator of the Planet $\mathrm{L}$ amusement park.

To manage the park better, the park requires all tourists to make reservations in advance. Xiao Lan can see the names of all reserved visitors in the system. Each visitor's name starts with an uppercase English letter, followed by $0$ or more lowercase English letters. Different visitors may have the same name.

Xiao Lan especially likes increasing things. Today, he decides to choose some of the reserved visitors to visit in the morning, and all other visitors to visit in the afternoon. For the visitors who visit in the morning, after keeping the reservation order, their names must be strictly increasing, i.e., the name earlier in the order is strictly smaller than the name later in the order.

A name $A$ is smaller than another name $B$ if there exists an integer $i$ such that the first $i$ letters of $A$ and the first $i$ letters of $B$ are the same, and the $(i+1)$-th letter of $A$ is smaller than the $(i+1)$-th letter of $B$. (If $A$ does not have an $(i+1)$-th letter but $B$ does, it is also considered that the $(i+1)$-th letter of $A$ is smaller than the $(i+1)$-th letter of $B$.)

As Xiao Lan's assistant, you need to arrange the visitors according to his idea, and you also want as many visitors as possible to visit in the morning. Please tell Xiao Lan which visitors should visit in the morning. If there are multiple plans, output the plan whose first morning visitor's name is the smallest. If there are still multiple plans, under the condition that the first name is the smallest, output the plan whose second morning visitor's name is the smallest. If there are still multiple plans, and so on, choose the plan with the smallest third, fourth, ... visitor names.

Input Format

The input contains a string that gives all visitors' names in reservation order, with no separators between adjacent names.

Output Format

Output the list of visitors who visit in the morning in reservation order, with no separators in between.

WoAiLanQiaobei

AiLanQiaobei

Hint

For $20 \%$ of the testdata, the total input length does not exceed $20$ letters.

For $50 \%$ of the testdata, the total input length does not exceed $300$ letters.

For $70 \%$ of the testdata, the total input length does not exceed $10000$ letters.

For all testdata, each name has length at most $10$ letters, and the total input length does not exceed $10^6$ letters.

Lanqiao Cup 2020 National Final B Group, Problem G.

Translated by ChatGPT 5