Все мы слышали захватывающие истории о приключениях Робина Гуда, который, будучи великолепным лучником, воровал деньги у богатых и раздавал их бедным.

В Кекландии проживает n человек, при этом у человека номер i изначально имеется c_i монет. Каждый день Робин Гуд отбирает 1 монету у самого богатого человека и отдаёт её самому бедному человеку (самому бедному, после того как он уже забрал 1 монету у самого богатого). Если самого богатого или самого бедного невозможно выбрать однозначно, то из подходящих вариантов Робин Гуд выбирает одного случайного. К сожалению, Робин Гуд уже стар и через k дней уйдёт на пенсию. Он решил провести все эти дни отбирая деньги у богатых и раздавая бендым.

После того как Робин Гуд отбирает монету у самого богатого, этот человек может стать самым бедным, и может даже так произойти, что Робин Гуд отдаст ему его монету назад. Например, если в какой-то день у всех жителей одинаковое количество монет, то и на следующий день у всех жителей также будет одинаковое количество монет.

Вам поручено найти разность количества денег у самого богатого и самого бедного человека через k дней. Обратите внимание, что случайность выбора среди самых богатых и самых бедных не влияет на ответ.