D - リーディングゼロ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 7

注意

この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

N 個の文字列 S_i が与えられます。S_i は数字のみからなる文字列です。

これらの文字列を 10 進法の数とみなして、値の小さい順にソートして出力してください。ただし、値が等しい数は、先頭につく 0 の個数が多い方を前にしてください。

制約

  • 1\leq N \leq 10^5
  • S_i の長さの和は 10^5 以下
  • S_i は数字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

N
S_1
\vdots
S_N

出力

与えられた文字列を指定された順序にソートし、改行区切りで出力せよ。


入力例 1

5
2
1
01
1
0010

出力例 1

01
1
1
2
0010

S_2,S_3,S_4 はいずれも値としては 1 ですが、先頭につく 0 の個数が多いものから順に出力してください。


入力例 2

6
1111111111111111111111
00011111111111111111111
000000111111111111111111
0000000001111111111111111
00000000000011111111111111
000000000000000111111111111

出力例 2

000000000000000111111111111
00000000000011111111111111
0000000001111111111111111
000000111111111111111111
00011111111111111111111
1111111111111111111111

与えられる文字列は非常に長い可能性があります。

Score : 7 points

Problem Statement

Given are N strings S_1, \ldots, S_N, each of which consists of digits.

Sort these strings as decimal integers in ascending order and print the result. If multiple strings are equal as integers, they should be in descending order of the numbers of leading zeros.

Constraints

  • 1\leq N \leq 10^5
  • The total length of S_i is at most 10^5.
  • S_i consists of digits.

Input

Input is given from Standard Input in the following format:

N
S_1
\vdots
S_N

Output

Print the strings after sorting them in the specified order, each in its own line.


Sample Input 1

5
2
1
01
1
0010

Sample Output 1

01
1
1
2
0010

As integers, S_2, S_3, and S_4 are all 1, but we ask you to print them in descending order of the numbers of leading zeros.


Sample Input 2

6
1111111111111111111111
00011111111111111111111
000000111111111111111111
0000000001111111111111111
00000000000011111111111111
000000000000000111111111111

Sample Output 2

000000000000000111111111111
00000000000011111111111111
0000000001111111111111111
000000111111111111111111
00011111111111111111111
1111111111111111111111

There may be extremely long strings.