You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

小精灵

说明

在一个神奇的转盘上，n个小精灵（编号从0到n-1）正在进行一场有趣的移动游戏。转盘上的位置也按照顺时针方向从0到n-1进行编号。最初，第0号小精灵站在第0号位置，第1号小精灵在第1号位置，依此类推。

游戏规则如下：每一轮中，第0号位置上的小精灵顺时针移动到第m号位置，第1号位置的小精灵移动到第m+1号位置，依此类推，第n−m号位置上的小精灵移动到第0号位置，第n-m+1号位置上的小精灵移动到第1号位置，直到第n-1号位置的小精灵顺时针移动到第m-1号位置。

现在，这个游戏已经进行了 $10^k$ 轮，你需要计算出编号为x的小精灵最终位于哪个位置。

输入格式

每组输入数据仅包含一行，包含四个整数 $n, m, k, x$，每两个整数之间用一个空格隔开。

数据规模

• 对于30%的数据，$0 < k < 7$；
• 对于80%的数据，$0 < k < 10^7$；
• 对于100%的数据，$1 < n < 1,000,000$，$0 < m < n$，$0 \leq x < n$，$0 < k < 10^9$。

输出格式

每组输出包含一行，表示经过 $10^k$ 轮后，编号为x的小精灵所在的位置编号。

样例

输入

10 3 4 5

输出

5