The store is having a New Year sale – prices of all goods are reduced by 25%. It turned out that initially all prices were divisible by 4, so after the price decrease, all prices are also expressed as an integer. In the evening before the sale, the merchandiser removed the price tags from all the goods and printed another price tag with a reduced price for each product. He left all the price tags on the table, hoping to hang them up in the morning. But when he came to the store in the morning, he found that the cleaning lady had mixed all the price tags together, and now he needs to separate the old price tags from the new ones.
Help him solve this problem.
Input
The first line of the input contains the total number of price tags N, 2 <= N <= 105, N – even number. The following N lines contain positive integers not exceeding 109, in non-decreasing order, one per line – numbers written on all price tags (both old and new). It is guaranteed that the input data is correct, that is, the solution exists.
Imprint
The program should output
N/2 integers in non-decreasing order – the cost of goods after price reduction.
Examples
| # |
Input |
Output |
Note |
| 1 |
6
30
40
42
45
56
60
|
30
42
45
|
Before the sale, the prices of the goods were 40, 56, 60, after the price reduction
these products have become equal to 30, 42, 45.
|