Description

$n$ friends (numbered from $0$ to $n-1$) sit in a circle to play a game. The $n$ positions are numbered clockwise from $0$ to $n-1$. Initially, friend $0$ is at position $0$, friend $1$ is at position $1$, and so on. The rules are as follows: in each round, the friend at position $0$ moves clockwise to position $m$, the friend at position $1$ moves to position $m+1$, and so on; the friend at position $n-m$ moves to position $0$, the friend at position $n-m+1$ moves to position $1$, ... , and the friend at position $n-1$ moves clockwise to position $m-1$.

Now, after a total of ${10}^k$ rounds, determine which position friend $x$ ends up at.

Input Format

One line containing four integers $n, m, k, x$, with a single space separating each pair of integers.

Output Format

One integer, the position index where friend $x$ is located after ${10}^k$ rounds.

10 3 4 5

5

Hint

For $30\%$ of the testdata, $0 < k < 7$.

For $80\%$ of the testdata, $0 < k < {10}^7$.

For $100\%$ of the testdata, $1 < n < {10}^6$, $0 < m < n$, $0 \le x \le n$, $0 < k < {10}^9$.

Translated by ChatGPT 5