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

На геном растений влияют гены X, Y и Z. Они взаимодействуют между собой следующим образом: каждый раз под действием катализатора все гены раздваиваются (каждый ген делится на два новых гена), после этого половина сформированных генов X и половина Y взаимодействуют, чтобы получить ген Z. Вторая половина X и половина Z формируют ген Y. И оставшиеся половины Y и Z производят ген X. Таким образом, если геном состоял из x₀, y₀, z₀ соответствующих генов, то после одного применения катализатора он будет состоять из x₁, y₁, z₁ генов, где x₁ = y₀ + z₀, y₁ = x₀ + z₀ и z₁ = x₀ + y₀.

Вероника исследует отношение генов X и Y. Для исследований ей нужно знать, на сколько гена X будет больше, чем гена Y после k применений катализатора. Ваша задача — написать программу, которая рассчитает x_k −y_k, где x_k и y_k — количество генов X и Y соответственно после k применений катализатора.

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

Во единственной строке дано четыре числа x, y, z и k (0 ≤ x, y, z, k ≤ 10¹⁸) — первоначальное количество генов X, Y и Z соответственно, а также количество применений катализатора.

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

В единственной строке выведите, на сколько гена X больше, чем гена Y после k применений катализатора.

Пример

Примечание

Во втором примере после одного применения катализатора будет 5 генов X и 6 генов Y. Соответственно, гена X на -1 больше, чем гена Y.