Remote Training on Programming

В данной задаче Вам придется побыть разработчиком программного обеспечения к распределенной системе. Система занимается хранением документов. Все документы в системе распределены по различным блокам, пронумерованным от 1 до N. Каждый такой блок имеет неограниченную емкость. Назовем состоянием блока количество документов в нем.

При добавлении новых документов в систему должно применяться правило равномерного заполнения: новый документ должен помещаться в наименее заполненный блок, а если таких блоков несколько, то в блок с наименьшим порядковым номером.

Вам дана система с заранее известным начальным состоянием блоков (которое может не быть результатом равномерного заполнения), то есть известно количество документов в каждом блоке Ki. Дальнейшее заполнение будут происходить по правилу равномерного распределения. Всего будет добавлено в систему еще M документов.

Вам необходимо сообщить о состоянии блоков системы после добавления в систему M новых документов.

Input

В первой строке входного файла располагается целое число N (1 <= N <= 1000) - количество блоков в системе. Вторая строка содержит N целых неотрицательных чисел K_i (0 <=K_i <= 10⁶), разделенных пробелами. Третья строка содержит число M (0 <= M <= 10¹²) - количество добавляемых документов.

Output

N целых чисел, разделенных пробелами - количество документов в каждом из блоков после дополнения системы M документами.

Sample

5
1 2 3 4 5
1

2 2 3 4 5

5
5 4 3 1 1
3

5 4 3 3 2

Примечание