Sofiia gave Anton an array of ! Although this array was not the first one he had seen, he did not consider it less interesting. After playing with the array, he did not notice how he broke it to a state where he could no longer restore the original.
He was very upset because there were almost countless ways to compose the initial array. However, he remembers an interesting property of the gift: , which means the sum of concatenations of all pairs of its elements, is \textbf{maximum} among all possible arrays made from these digits consisting of the same elements, as the gift.
In other words, we take all pairs of positions and such that is not to the left of (). And add to the sum , where means the number that will result if we write the numbers and in order (or ). This is called the concatenation of and .
For example, if Anton had an array , then the sum would be equal to = .
Help Anton and print an array that has this property. If there are multiple answers, any of them can be output.
输入格式
The first line contains integers () --- where corresponds to the number of digits in the initial array.
It is guaranteed that the sum of all numbers is greater than zero.
输出格式
Print an array consisting of elements, and has the same properties as the array given by Sophia.
样例
样例输入 1
0 0 0 0 0 2 0 0 0 0
样例输出 1
5 5
样例输入 2
1 0 1 1 0 0 0 0 0 0
样例输出 2
3 2 0
数据范围与提示
In the second example, there are such possible arrays:
