유전체

볼리바르 트래스크는 수호자들을 더 뛰어나게 만들기 위해 실험실에서 돌연변이체의 유전체를 연구한다.

돌연변이체의 유전체는 유전자 $X$, $Y$, $Z$의 영향을 받는다. 이 유전자들은 다음과 같이 상호작용한다. 촉매가 작용할 때마다 모든 유전자가 절반으로 나뉜다. 그다음 생긴 $X$의 절반과 $Y$의 절반이 결합해 $Z$를 만든다. $X$의 나머지 절반과 $Z$의 절반은 $Y$를 만든다. 마지막으로 남은 $Y$의 절반과 $Z$의 절반은 $X$를 만든다.

유전체에 $X$가 $x_0$개, $Y$가 $y_0$개, $Z$가 $z_0$개 있다면, 촉매를 한 번 적용한 뒤에는 $X$가 $x_1$개, $Y$가 $y_1$개, $Z$가 $z_1$개가 된다. 여기서 $x_1 = y_0 + z_0$, $y_1 = x_0 + z_0$, $z_1 = x_0 + y_0$이다.

한 줄에 정수 $x$, $y$, $z$, $k$가 공백으로 구분되어 주어진다 ($0 \le x, y, z, k \le 10^{18}$). 차례대로 처음 $X$, $Y$, $Z$ 유전자의 개수와 촉매를 적용하는 횟수이다.

촉매를 $k$번 적용한 뒤 $X$ 유전자의 개수에서 $Y$ 유전자의 개수를 뺀 값 $x_k - y_k$를 한 줄에 출력한다.

두 번째 예제에서 촉매를 한 번 적용하면 $X$ 유전자는 5개, $Y$ 유전자는 6개가 된다. 따라서 $X$ 유전자는 $Y$ 유전자보다 $-1$만큼 많다, 즉 1개 적다.