Problem 21407 --圆圈报数(II)(输出第几个出队的人)

21407: 圆圈报数(II)(输出第几个出队的人)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 22  Solved: 3
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

小明已经深刻了解了如何不需要模拟出队过程,通过递推得到n个圆圈报数最后一个胜利者的序号,但突然小红问他第 p个出队的人的号码,小明觉得还是有点困难,你能帮他解决吗?

原问题整理为:

n 个人按顺时针围成一圈从1开始按顺序顺序编号,首先先把第m号的人出队,然后从m+1号开始按1、2、3 、....、k按顺时针报数,报 k 者退出圈外,其余的人再从1、2、3 、....、k 报数,报 k 的人再退出圈外,依次类推。请告诉小明第p个出队的人的序号。

Input

有多行数据,每行数据包含一组 n  k   m   p

当遇到0 0 0 0时,数据结束。其中满足2 ≤ n ≤ 10000, 1 ≤ k ≤ 10000, 1 ≤ m , p n, 测试数据的行数小于100.


Output

输出每行数据中所对应的第 p 个人出队的序号。

Sample Input

10 3 3 1
10 3 3 10
0 0 0 0

Sample Output

3
4

HINT

Source

[Submit][Status]