TopCoder

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

50.0% (1/2)

Tags

Description

大河想要為他的新商品命名,為了讓他的新商品能最早的被人發現,大河希望他的新商品名稱的字典序越小越好。

雖然說大河已經想到了一個名稱 $s$,但為了想要聽聽更多人的想法,便決定走訪知名的 $n$ 家設計公司尋求建議。

每一家設計公司都會提供一個新的名稱 $s'$,如果新的名稱 $s'$ 的字典序比大河屬意的名稱還要小,那大河就會將心中屬意的名稱替換為 $s'$,並繼續向下一間設計公司詢問;但如果新的名稱的字典序大於或等於大河屬意的名稱,大河就會大聲的喊出新的名稱 $s'$ 並要求退費。

注意,只要大河離開了某間設計公司,就再也沒辦法利用大喊該公司提供的命名的方式來要求退費了,也就是說,只有否決新的提案時,才需要大喊新的名稱並退費

Input Format

第一行有一個整數 $n\ (1\le n\le 10^ 5)$ 跟一個字串 $s$,$s$ 的長度不超過 $60$,代表大河要走訪個設計公司數量以及一開始屬意的新商品名稱,兩者之間以空白分隔。

接下來 $n$ 行之中,第 $i$ 有一個字串 $s'$ 代表第 $i$ 間設計公司提供的商品名稱,$s'$ 的長度不超過 $60$。

保證所有的字串皆由大、小寫英文字母所組成。

Output Format

對於每一個設計公司提供的名稱 $s'$,如果 $s'$ 的字典序小於大河心中屬意的 $s$,就把大河屬意的 $s$ 替換為 $s'$,否則就輸出 $s'$ 並換行,代表喊出名稱並退費。

最後一行請輸出最後大河屬意的商品名稱。

Sample Input 1

3 cookies
aookies
bookies
aoo

Sample Output 1

bookies
aoo

Sample Input 2

3 candy
candy
apple
apple

Sample Output 2

candy
apple
apple

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2