Задача 04. Родная улица моя ≡

Условие

Когда весна придёт, не знаю,

Пройдут дожди... Сойдут снега...

Но ты мне, улица родная,

И в непогоду дорога.

...

На этой улице подростком

Гонял по крышам голубей,

И здесь, на этом перекрёстке,

С любовью встретился своей.

...

Алексей Фатьянов, "На Заречной улице", 1955 г.

Песня из фильма "Весна на Заречной улице"

На Заречной улице в один ряд расположено n домов, на крышах которых сидят d_i голубей. Сталевар-передовик Саша, пробегая вдоль домов, пугает птиц, которые перелетают на крыши следующих по порядку домов по такому правилу:

Пусть на крыше дома с номером i сидят d голубей. Поднявшись в воздух, они распределяются по крышам оставшихся n − i домов по ⌊ dn − i⌋ штук, где скобки означают округление вниз до целой части. Не делящийся остаток целиком перелетает на крышу следующего i + 1 дома. Для определенности считайте, что скорость птиц существенно превосходит скорость Саши и они успевают перераспределиться до того момента, когда он добежит до следующего дома.

Пробежав мимо первых m домов, молодой рабочий встретит на перекрестке выпускницу пединститута Таню, остановится как вкопанный, и в жизни пернатых наконец-то наступит спокойствие.

До входным данным определите итоговую рассадку птиц.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество домов на улице. Во второй строке через пробел расположены n неотрицательных целых чисел d_i — начальная рассадка голубей по крышам. Третья строка входного файла содержит натуральное число m — количество домов на улице, мимо которых пробежит Саша.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

Формат выходных данных

Выведите через пробел n − m неотрицательных целых чисел d_i — конечную рассадку голубей по крышам оставшихся домов.

Ограничения

1 ≤ m < n ≤ 10⁵

0 ≤ d_i ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при m = n − 1, получат не менее 10 баллов.

Решения, верно работающие при d_i ≤ 100, получат не менее 20 баллов.

Решения, верно работающие при n ≤ 1000, получат не менее 20 баллов.

Пояснение к примеру

В примере n = 5 домов. На крыше первого дома 10 голубей, второго — 0, третьего — 2, четвертого — 7 и пятого — 3. Саша пробежит мимо первых трех домов из пяти.

Первые десять голубей перелетят на крыши следующих четырёх домов. Так как ⌊ 104⌋  = 2, на каждую из следующих крыш перелетит по два голубя, а еще два (не делящийся остаток) перелетит на крышу следующего дома. Теперь голуби сидят так: 0, 4, 4, 9, 5.

Когда Саша будет пробегать мимо второго дома, четыре голубя перелетят на крыши следующих трёх домов. Так как ⌊ 43⌋  = 1, на каждую из следующих крыш перелетит по одному голубю, а еще один (не делящийся остаток) перелетит на крышу следующего дома. Теперь голуби сидят так: 0, 0, 6, 10, 6.

Когда Саша будет пробегать мимо третьего дома, шесть голубей перелетят на крыши следующих двух домов. Так как ⌊ 62⌋  = 3, на каждую из следующих крыш перелетит по три голубя. Не делящийся остаток равен нулю. Теперь (и окончательно) голуби сидят так: 0, 0, 0, 13, 9.

Примеры тестов

5
10 0 2 7 3
3

13 9