Поликарп собрал всех своих друзей на чаепитие, чтобы отметить важное событие. У него есть n чашек, по одной для каждого из n друзей, объемами a1, a2, ..., an. Его чайник вмещает в себя w миллилитров чая (w ≤ a1 + a2 + ... + an). Поликарп хочет разлить чай по чашкам таким образом, чтобы:
- Каждая чашка была заполнена не меньше, чем на половину своего объема
- В каждой чашке было налито целое число миллилитров чая
- Весь чай из чайника был разлит по чашкам
- Ни один из друзей не расстроился
Известно, что обладатель чашки i расстроится, если существует такая чашка j, что в i налили меньше чая, чем в j, но ai > aj.
Для каждой чашки выведите, сколько миллилитров чая должно быть в нее налито. Если невозможно разлить весь чай таким образом, чтобы удовлетворить все условия, то выведите -1.
Выходные данные
Выведите для каждой чашки, сколько миллилитров чая должно быть в нее налито. Если ответов несколько, выведите любой из них.
Если невозможно разлить весь чай таким образом, чтобы удовлетворить все условия, то выведите -1.
Примечание
В третьем примере необходимо налить в первую чашку не меньше 5 миллилитров, во вторую — не меньше 4, в третью — не меньше 5. В сумме получается 14 миллилитров, что превосходит количество чая в чайнике.