29103번 - Геном 다국어

문제

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

На геном мутанта влияют гены 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.