DUCKGAME - Duck Game

In a large farm, N ducks are standing and making a big circle. They are numbered 1 to N. Their position are sorted in clockwise and the Nth duck is adjacent to the first duck.

Then, they will make a game with the following rules :

  • the game is played in N rounds
  • first round is to decide who is the Nth winner, second round is to decide who is the (N-1)th winner and so on until Nth round is to decide who is the champion (1st winner). formally, ith round is to decide who is the (N-i+1)th winner
  • in each round i (1 ≤ i ≤ N), Mr. Dengklek as a moderator counting the ducks in clockwise direction. Aith duck will be the winner in this round, that duck will not play anymore and get out from the circle
  • in the first round, Mr. Dengklek starts counting from the first duck. then in ith round (1 < iN), Mr. Dengklek will start counting from the duck after the previous round winner

A is an array of N integer with A1 = L. For 1 < i N, if Ai-1 = R then Ai = L. Otherwise, Ai = Ai-1 + 1.

Because the number of ducks is too large, so the game won't be finished even though in one century. Here, you are to find the fastest algorithm to know the Mth winner (with given N, L, and R) in less than 2 seconds.


Input contains 2 lines only.

In the first line, given N and M separated by a white space.

The last line contain 2 integers represent L and R.


The only line contain one number represent the Mth winner of that game.


1 ≤ M N ≤ 1018

1 ≤ L ≤ R ≤ 1018

N-M ≤ 108 or R ≤ 105


5 3
2 4

A = {2,3,4,2,3}

round 1 :
    1 - 2
    second duck become the 5th winner and get out from the game
round 2 :
    3 - 4 - 5
    start counting from 3th duck because the previous winner is the second duck
round 3 :
    1 - 3 - 4 - 1
    after the last duck is the first duck because they are standing in a circle
    second duck and 5th duck skipped because they are not playing anymore
round 4 :
    3 - 4
    A4 = L = 2 because A3 = 4 = R
round 5 :
    3 - 3 - 3
    3th duck is the champion


Added by:Amnu
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:own problem