Reversed-Element Sort

Time limit1sMemory limit128 MB

Summary

Reverse the digits of each of n positive integers, drop leading zeros, then print the reversed values in ascending order.

Level: Easy3 of 10
Topics: Sorting, Math, Implementation
Solved: No attempts yet

Problem

You are given a set whose elements are all positive integers. For each element, reverse the order of its digits, then sort the reversed values in ascending order.

When an element is reversed and a 0 ends up in front (that is, when the original number ends in 0), drop all of those leading zeros. For example, reversing 90100 gives 00109, and after dropping the leading zeros it becomes 109.

Input

The first integer is $n$ ( $1 \le n \le 10^6$ ), the number of elements that follow. Then $n$ elements are given, separated by whitespace (spaces or newlines). A single line may contain several elements.

Each element is a positive integer no greater than $10^{12}$ .

Output

Reverse every element, sort the resulting values in ascending order, and print them one per line.

Examples3

Example 1

Input

10 5 2233
1601 90100 13009 802
50000000
301 7654321
210

Expected output

Example 2
Input
```
1 5
```
Expected output
```
5
```
Example 3
Input
```
6 210 120
300 3
30 21
```
Expected output
```
3
3
3
12
12
21
```