Description

暑假开始了，夏令营的日子也来临了。住进宿舍的第一天晚上，小A和新认识的同学们在宿舍里玩起了转圈游戏。编号为 $0$ ~ $n-1$ 的 $n$ 个小伙伴围成一圈，他们坐的位置也被编号为了 $0$ ~ $n-1$ 。最初，第 $0$ 号小伙伴在第 $0$ 号位置，第 $1$ 号小伙伴在第 $1$ 号位置......依此类推。

游戏规则如下：每一轮第 $0$ 号位置上的小伙伴顺时针走到第 $m$ 号位置，第 $1$ 号位置小伙伴走到第 $m+1$ 号位置....依此类推，第 $n−m$ 号位置上的小伙伴走到第 $0$ 号位置，第 $n-m+1$ 号位置上的小伙伴走到第 $1$ 号位置......第 $n-1$ 号位置上的小伙伴顺时针走到第 $m-1$ 号位置。

这个游戏实在太好玩了，以至于小A和他的小伙伴们玩了 $10^k$ 轮，请问 $x$ 号小伙伴最后走到了第几号位置。

Input Format

从文件 circle.in 中读取数据。

第一行有四个由单个空格分隔的整数 $n$ , $m$ , $k$ , $x$ ，意义如题所示。

Output Format

输出到文件 circle.out 中去。

仅一行一个整数，表示 $10^k$ 轮后第 $x$ 号小伙伴的最终位置编号。

Sample

样例输入1

10 3 4 5

样例输出1

5

Hint

对于 $30\%$ 的数据，$0 \le k \le 7$

对于 $80\%$ 的数据，$0 \le k \le 10^7$

对于 $100\%$ 的数据，$1 \le n \le 1,000,000$ ，$0 \le m \le n$ ，$0 le x \le n$ ，$0 \le k \le 10^9$.