Геном

Боливар Траск изучает геном мутантов в своей лаборатории, чтобы сделать своих Стражей ещё более совершенными.

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

Траск исследует отношение генов X и Y. Для исследований ему нужно знать, на сколько гена X будет больше, чем гена Y после $k$ применений катализатора. Ваша задача --- написать программу, которая рассчитает $x\_k - y\_k$, где $x\_k$ и $y\_k$ --- количество генов X и Y соответственно после $k$ применений катализатора.

Во единственной строке входного файла дано четыре числа $x$, $y$, $z$ и $k$ ($0 \le x, y, z, k \le 10^{18}$) --- первоначальное количество генов X, Y и Z соответсвенно, а также количество применений катализатора.

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

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