Description

$n$个$MM$（编号从$0$到$n-1$）围在一圈“丢手绢”。按照顺时针方向给$n$个位置编号，从$0$到$n-1$。最初，第$0$号$MM$在第$0$号位置，第$1$号$MM$在第$1$号位置，$\dots$，依此类推。

游戏规则如下：每一轮第$0$号位置上的$MM$顺时针走到第$m$号位置，第1号位置$MM$走到第$m+1$号位置，$\dots$，依此类推，第$n−m$号位置上的$MM$走到第$0$号位置，第$n-m+1$号位置上的$MM$走到第$1$号位置，$\dots$，第$n-1$号位置上的$MM$顺时针走到第$m-1$号位置。现在，一共进行了$10^k$轮，请问$x$号$MM$最后走到了第几号位置。

Format

Input

输入共$1$行，包含$4$个整数$n$、$m$、$k$、$x$，每两个整数之间用一个空格隔开。

Output

输出共$1$行，包含$1$个整数，表示$10^k$轮后$x$号$MM$所在的位置编号。

Samples

10 3 4 5

5

Hints

对于$30\%$的数据，$0\lt𝑘\lt7$； 对于$80\%$的数据，$0\lt𝑘\lt10^7$；

对于$100\%$的数据，$1\lt𝑛\lt1,000,000$，$0\lt𝑚\lt𝑛$，$0\le x$ ，$0\lt𝑘\lt10^9$。