← 返回题目列表

Codeforces · 1056/G

G. 乘坐地铁

中文机器翻译题面 查看原题

早上电车路线出现问题,阿尔卡迪决定乘坐地铁回家。对于阿尔卡迪来说幸运的是,该市只有一条地铁线。

不幸的是,对于阿尔卡迪来说,这条线是圆形的。这意味着车站从 $$$1$$$ 到 $$$n$$$ 进行枚举,并且任意一对连续车站之间以及车站 $$$1$$$ 和车站 $$$n$$$ 之间都存在隧道。顺时针方向行驶的列车按 $$$1 \to 2 \to 3 \to \ldots \to n \to 1$$$ 的顺序进站,而逆时针方向行驶的列车则按相反的顺序进站。

编号从 $$$1$$$ 到 $$$m$$$ 的车站的内饰大多为红色,而编号从 $$$m + 1$$$ 到 $$$n$$$ 的车站内饰为蓝色。 Arkady 在 $$$s$$$ 站进入地铁,并决定使用以下算法来选择回家的路。

1. 最初他脑子里有一个正整数$$$t$$$。
2.如果当前车站有红色内饰,则乘坐顺时针方向的火车,否则乘坐逆时针方向的火车。
3. 他恰好乘坐了火车上的 $$$t$$$ 站并离开了火车。
4. 他将 $$$t$$$ 减一。如果 $$$t$$$ 仍然为正,则返回步骤 $$$2$$$。否则他就会退出地铁。

你已经意识到这个算法很可能不会把阿尔卡迪带回家。找到他要离开地铁的车站,以便您可以继续帮助他。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \le n \le 10^5$$$, $$$1 \le m < n$$$) — 车站总数和内部为红色的车站数量。

第二行包含两个整数 $$$s$$$ 和 $$$t$$$ ($$$1 \le s \le n$$$, $$$1 \le t \le 10^{12}$$$) — 起始站和 $$$t$$$ 的初始值。

输出

输出唯一的整数——Arkady 离开地铁的车站。

示例

输入 #1

10 4
3 1

输出 #1

4

输入 #2

10 4
3 5

输出 #2

4

输入 #3

10543 437
5492 1947349

输出 #3

438

注意

考虑第一个例子。有 $$$10$$$ 站,其中前 $$$4$$$ 是红色的。 Arkady 从车站 $$$3$$$ 开始,值 $$$t = 1$$$,因此只需以顺时针方向乘坐 $$$1$$$ 车站,最终到达车站 $$$4$$$。

在第二个示例中,地铁与第一个示例中的相同,但 Arkady 从车站 $$$3$$$ 开始,值 $$$t = 5$$$。

- 这是一个红色车站,所以他顺时针方向乘坐 $$$5$$$ 车站,并在 $$$8$$$ 车站下车。
- 这是一个蓝色车站,所以他逆时针方向乘坐 $$$4$$$ 车站,并在 $$$4$$$ 车站出发。
- 这是一个红色车站,所以他顺时针方向乘坐 $$$3$$$ 车站,并在 $$$7$$$ 车站出发。
- 这是一个蓝色车站,所以他逆时针方向乘坐 $$$2$$$ 车站,并在 $$$5$$$ 车站出发。
- 这是一个蓝色车站,所以他逆时针方向乘坐 $$$1$$$ 车站,并在 $$$4$$$ 车站出发。