406432: GYM102409 D Lottery Ticket

Diego is about to enter a raffle, however this raffle has some weird properties, instead of choosing the winning ticket at random with each ticket having the same probability of winning, they will chose which ticket wins based on a process, you have to help Diego guarantee that he will win the lottery!

Every ticket has an ID, all IDs are different and are bigger or equal to 1, additionally if ticket with ID $$$X$$$ exists all tickets with IDs $$$[1,X-1]$$$ must exist as well. In order to choose a winning ticket they will first sort all the tickets from left to right in ascending order by ID, then choose a starting ticket $$$S$$$ and some integer $$$K$$$. On each step they will move $$$K$$$ tickets to the right and eliminate the ticket where they land. Keep in mind that once a ticket is eliminated it's not in the list of tickets anymore, which means that if the current ticket has ID $$$X$$$, by moving $$$K$$$ tickets to the right, the ticket we land on may not have ID $$$X+K$$$ if some tickets in the middle already got eliminated. Additionally, when the end of the list is reached the next ticket is the first in the list, you can think of the list as cyclic.

Once a ticket gets eliminated the new starting ticket becomes the one to the left of the eliminated ticket (if the eliminated ticket was the first then the last one becomes the starting ticket). This process will continue until there is only 1 ticket left, that ticket will be crowned the winning ticket! Help Diego find the ID of the winning ticket.

An integer T $$$(1 \le T \le 10^5)$$$ the amount of test cases.

Followed by T lines, each with 3 integers $$$N, S, K$$$ $$$(1 \le S \le N \le 10^{18}, 1 \le K \le 10)$$$. Where $$$N$$$ represents the biggest ID that a ticket has, $$$S$$$ the starting position and $$$K$$$ the amount of tickets to move to the right before eliminating the next ticket.

$$$T$$$ integers, one per test case (in the order they were provided, of course). The ID of the winning ticket.

1
5 3 2

1

In the sample case, the following steps happen:

Step 1: [1,2,3,4,5], current position=3

Step 2: [1,2,3,4], current position=4

Step 3: [1,3,4], current position=1

Step 4: [1,3], current position=2

Step 5: [1] 1 is the winning ticket!