Description

Little Mirko does not pay attention in math class, so the teacher decided to give him a boring homework assignment over the weekend.

The teacher gave him a text consisting of $n$ lines, containing only digits and lowercase letters. Mirko must find all numbers in the text and output them in non-decreasing order. He also has to remove any leading zeros that a number in the text may contain.

These numbers can be determined by scanning the text and always taking the largest possible number, i.e., delimited only by letters or the start/end of a line. For example, the final output for 01a2b3456cde478 is 1, 2, 478, 3456.

Since Mirko solves problems as slowly as a snail, he asks you to write a program to finish the task quickly, so that he can go play with Slavko as soon as possible.

Input Format

The first line contains an integer $n$, the number of lines in the text.

The next $n$ lines each contain a string.

Output Format

Output one integer per line, representing a number in the text (from small to large).

2
lo3za4
01

1
3
4

4
43silos0
zita002
le2sim
231233

0
2
2
43
231233

4
01bond
02james007
03bond
04austinpowers000

0
1
2
3
4
7

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 100$, each string has length at most $100$, the total count of numbers in the text is at most $500$, and the input contains only lowercase letters and digits.

Notes

• This problem is worth $60$ points in total.
• Translated from COCI2010-2011 CONTEST #2 NAPOR. Translator:
  https://www.luogu.com.cn/user/115711

Translated by ChatGPT 5