Любите ли вы лето? Жители Берляндии любят. А особенно они любят в жаркую летнюю погоду полакомиться мороженым. Так и в этот летний день перед киоском с мороженым образовалась огромная очередь из n берляндцев. Известно, что у каждого из них есть с собой некоторая сумма берляндских долларов. Жители Берляндии сговорчивые, поэтому каждый берляндец всего за 1 доллар согласен поменяться местом с тем, кто стоит в очереди непосредственно за ним. Более формально, если человек a стоял сразу за человеком b, то человек a может заплатить человеку b 1 доллар, и тогда a и b поменяются местами. Разумеется, если у человека a нулевое количество долларов, то он не может поменяться местами с b.
Жители Берляндии — люди странные. В частности, они расстраиваются, когда в очереди перед ними стоит кто-то со строго меньшей суммой денег.
Сможете ли вы помочь жителям Берляндии упорядочиться в очереди так, чтобы все они были счастливы? Счастливый берляндец — это тот, который стоит в очереди первым, либо тот, впереди которого стоит другой житель с не меньшим количеством долларов. Учтите, что берляндцы — люди принципиальные, и согласны меняться местами только указанным выше способом.
Выходные данные
Если невозможно сделать так, чтобы все берляндцы стали счастливы, выведите ":(" без кавычек. В противном случае в единственной строке через пробел выведите n целых чисел, i-е из которых должно равняться количеству денег, которое будет у человека, оказавшегося на позиции i в новой очереди. Если существует несколько ответов, выведите любой из них.
Примечание
В первом примере два жителя должны поменяться местами, после чего у первого жителя станет 10 монет и он будет в начале очереди, а у второго - 9 монет, и, соответственно, он будет в конце очереди.
Во втором втором тесте добиться требуемого невозможно
В третьем примере первый человек может поменяться местами со вторым, тогда количества долларов у них будет следующими: 4 11 3, потом второй (в новой очереди) поменяется с третьим, и результирующие количества долларов будут равны: 4 4 10. В такой очереди все будут счастливы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
11 8
|
9 10
|
|
2
|
5
10 9 7 10 6
|
:(
|
|
3
|
3
12 3 3
|
4 4 10
|