$n$ people (numbered from $0$ to $n-1$) are sitting in a circle playing a game. The $n$ positions are numbered clockwise from $0$ to $n-1$. Initially, person $0$ is at position $0$, person $1$ is at position $1$, and so on.
The rules of the game are as follows: in each round, the person at position $0$ moves clockwise to position $m$, the person at position $1$ moves to position $m+1$, and so on. Generally, the person at position $i$ moves to position $(i + m) \pmod n$.
Now, after $10^k$ rounds have been played, determine the position number of person $x$.
Input
The input consists of a single line containing four integers $n, m, k, x$, separated by spaces.
Output
Output a single integer representing the position number of person $x$ after $10^k$ rounds.
Examples
Input 1
10 3 4 5
Output 1
5
Constraints
- For $30\%$ of the data, $0 < k < 7$;
- For $80\%$ of the data, $0 < k < 10^7$;
- For $100\%$ of the data, $1 < n < 1,000,000$, $0 < m < n$, $0 \le x < n$, $0 < k < 10^9$.