В отличие от Рыцарей Круглого Стола, Рыцари Многоугольного Стола обделены благородством и с радостью убьют друг друга. Однако каждый рыцарь обладает своей силой, и один рыцарь может убить другого только если его сила больше, чем сила жертвы. Однако даже такого рыцаря будет мучить совесть, поэтому рыцарь может убить максимум \(k\) других рыцарей.
Также у каждого рыцаря есть некоторое количество монет. При убийстве рыцарь может забрать все монеты своей жертвы.
Сейчас каждый рыцарь задумался: а какое наибольшее количество монет у него может оказаться, если убивать других рыцарей будет только он?
Вам предстоит ответить на этот вопрос для каждого рыцаря.
Выходные данные
Выведите \(n\) чисел — наибольшее количество монет у каждого рыцаря.
Примечание
Рассмотрим первый пример.
- Первый рыцарь самый слабый, он не может никого убить, поэтому у него максимум может быть только одна монета.
- Второй рыцарь может убить первого и забрать его монету в дополнение к двум своим.
- Третий рыцарь сильнее всех, но так как он максимум может убить \(k = 2\) рыцарей, то выгоднее всего забрать монеты у второго и четвертого рыцаря: \(2+11+33 = 46\).
- Четвертый рыцарь должен забрать монеты у первого и второго: \(33+1+2 = 36\).
Во втором примере первый рыцарь не может никого убить, а все остальные должны убить одного рыцаря, имеющего номер, на один меньший.
В третьем примере всего один рыцарь, он не может никого убить, хотя очень хочет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
4 5 9 7
1 2 11 33
|
1 3 46 36
|
|
2
|
5 1
1 2 3 4 5
1 2 3 4 5
|
1 3 5 7 9
|
|
3
|
1 0
2
3
|
3
|