题目描述

33 来到一个环形游乐场，这里有 $n$ 个格子，按顺时针方向依次编号为 $1,2,\ldots,n$。编号为 $n$ 的格子的顺时针下一个格子是编号为 $1$ 的格子。

33 最初站在编号为 $s$ 的格子上。每次跳跃，他都会沿顺时针方向前进 $k$ 格，也就是经过 $k$ 条相邻格子之间的边。起点不计入前进的格数，前进过程中可以绕过起点，也可以绕行多圈。

例如，当 $n=8$ 时，从编号为 $7$ 的格子顺时针前进 $3$ 格，会依次经过 $8,1,2$，最后到达编号为 $2$ 的格子。

请你求出连续跳跃 $t$ 次后，33 所在格子的编号。如果 $t=0$，表示他没有进行跳跃。

输入格式

一行四个整数 $n,s,k,t$，分别表示格子总数、起点编号、每次前进的格数和跳跃次数。

输出格式

一行一个整数，表示完成所有跳跃后所在格子的编号。

8 7 3 2

5

6 4 10 3

4

12 9 5 0

9

样例解释

样例 1：第一次跳跃从 $7$ 到达 $2$，第二次跳跃从 $2$ 到达 $5$。

样例 2：每次跳跃前进 $10$ 格，可以跨过一整圈。三次跳跃后依次到达 $2,6,4$，最终回到起点。

样例 3：跳跃次数为 $0$，因此仍然站在起点 $9$。

数据规模与约定

对于 $100\%$ 的数据，$2\le n\le 10^9$，$1\le s\le n$，$1\le k\le 10^9$，$0\le t\le 10^{18}$。

• 子任务 1（30 分）：保证 $0\le t\le 100$。
• 子任务 2（30 分）：保证 $0\le t\le 10^6$。
• 子任务 3（40 分）：没有特殊限制。