- Описание
- Отправленные решения
591. Надежный счетчик
Для подсчета количества запусков программы в офлайн-режиме сделали счетчик:
- Показание счетчика в каждый момент времени $-$ это отсортированная по неубыванию последовательность $n$ чисел $a_1 \le a_2 \le \ldots \le a_n$.
- При каждом запуске программы состояние счетчика изменяется: $a_1$ заменяется суммой $k$ минимальных элементов последовательности,т.е. $\sum\limits_{i=1}^{k}a_i$, и последовательность сортируется.
Зная начальное состояние счетчика и количество операций изменения счетчика $r$, найдите итоговую последовательность, задающую состояние счетчика.
Гарантируется, что во всех тестах значения элементов последовательности не выходят за пределы диапазона $[-10^{12}..10^{12}]$.
Формат ввода
В первой строке записаны три целых числа $n$, $k$, $r$ ($1 \le n, k, r \le 200\,000$, $k \le n$) $-$ длина последовательности элементов счетчика, количество участвующих в изменении счетчика элементов последовательности, количество операций изменения счетчика.
Во второй строке записаны $n$ целых чисел $a_i$ ($-1\,000\,000 \le a_i \le 1\,000\,000$) $-$ начальные элементы последовательности, задающей состояние счетчика. Последовательность отсортирована в порядке неубывания элементов.
Формат вывода
Выведите $n$ чисел $-$ элементы последовательности, задающей состояние счетчика, после $r$ изменений. Выводите числа, разделяя их пробелами, в неубывающем порядке.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
2 2 5
1 1
8 13
Пример 2
5 3 4
0 0 0 1 2
0 0 0 1 2
Пример 3
10 3 100
1 2 3 4 5 6 7 8 9 10
604466 686144 781715 890453 1010587 1140842 1282129 1438574 1617218 1826247