Problem Statement

There is a pseudorandom number generation method called the linear congruential generator. Using positive integers $a, b, m$, it generates random numbers by the recurrence $x_{i+1}=ax_i+b \pmod{m}$. For example, when $a=3, b=1, m=7, x_0=0$, we get $x_1=1, x_2=4, x_3=6, x_4=5, x_5=2, x_6=0, x_7=1, \dots$.

The modulo operation is usually slow, but when $m=2^{32}$, computing $ax_i+b$ with a 32-bit unsigned integer type yields the remainder through overflow, so it can be computed quickly. In this case, it is known that the maximum period $2^{32}$ is achieved when $a$ is an integer whose remainder when divided by $4$ is $1$ and $b$ is odd. From here on, let $m=2^{32}$.

To implement a die, we need random numbers such that the integers from $1$ to $6$ appear with roughly equal probability, so the die roll is defined as the remainder of $x_i$ divided by $6$, plus $1$.

Takahashi and Aoki decided to use this die to play the following sugoroku game.

Both start on square $0$. They take turns rolling the die, with Takahashi going first, and each advances by the number rolled. If the square a player lands on is odd, the player gets a black stone; if it is even, the player gets a white stone. This is repeated $N$ times, and a player earns $1$ point for each pair of one black stone and one white stone.

For example, when $N$ is $3$ and the rolls are $1, 3, 2, 6, 4, 5$, Takahashi lands on squares $1, 3, 7$ and gets $3$ black stones, while Aoki lands on squares $3, 9, 14$ and gets $2$ black stones and $1$ white stone. Their scores are $0$ points and $1$ point, respectively.

Given $a, b, x_0, N$, find the scores of Takahashi and Aoki. Note that the first die roll is the remainder of $x_1$ divided by $6$, plus $1$.

Input

$a\ b\ x_0\ N$

All inputs are integers.
$0 \le a, b, x_0, N \lt 2^{32}$
The remainder of $a$ divided by $4$ is $1$.
$b$ is odd.

Output

Print the scores of Takahashi and Aoki separated by a space. Print a newline at the end.

Sample

5 1 1 1

0 0

3000000001 3000000001 3000000001 0

0 0