CLSLDR - Class Leader


This is new year in Planet X and there is something special! A classroom in this planet is looking for a new class leader using an unique game!

These are the ways how the game is played.

  1. There are n students in the class. Each student is labeled from 1 (first student) to n (last student).
  2. A paper is given to m-th student.
  3. The next o-th student who gets the paper quits the game.
  4. The paper is passed until there is one last student who hasn't quitted the game.
  5. The student becomes the class leader.

Now, your task is to find the number of such student.

Input

The first line contains a number T (0 <= T <= 106).

Each of the next T lines contains 3 integers which are n (0 < n <= 103), m, o (0 < m, o <= n) and are separated by a single space.

Output

For each test cases, print the required answer.

Example

Input:
2
4 1 2
5 2 3

Output:
2
1

Explanation for Test Case 1

  • 1 2 3 4 → The paper is being held by student 1. Pass the paper by 2 students. Now, the paper is being held by student 3.
  • 1 2 4 → Student 3 quits. Pass the paper by 2 students. Now, the paper is being held by student 1.
  • 2 4 → Student 1 quits. Pass the paper by 2 students. Now, the paper is being held by student 4.
  • 2 → Student 4 quits. Student 2 becomes the class leader.

hide comments
farook_heroes: 2021-08-10 12:46:58

How the second test case in output is 1 pls say if anyone knows

lighted: 2020-09-14 23:22:15

I like constraints for this problem! O(n) dp solution for each case gives TLE. Should do extra dp memoization or tabulation+precalculation. Since max value of n & k is 1000 we have O(1000*1000) dp solution in worst. No matter that value of T can be 10^6. Accepted in 0.32s with fast IO of cin/cout.

amit013, don't be so stupid to blame author of such nice problem. I like Spoj for problems with most possible tight constraints. Such problems force us to find solutions with most efficient algorithms.

Last edit: 2020-09-20 22:19:57
delta01: 2019-10-06 16:09:01

time limit exceeded problem .. dont know where to reduce complexity

Last edit: 2019-10-06 18:25:02
amit013: 2019-02-26 23:09:38

Please remove this problem if you don't want us to be able to solve it. I have never seen so stupid time limit.
CPP is not working even with fast IO.
Really frustrated with these kind of problems by Spoj.

Last edit: 2019-02-26 23:11:02
anonymous: 2017-02-22 09:45:36

It looks like the input test cases do not satisfy given constraints (probably last one):

0 <= T <= 10^6
0 < n <= 10^3
0 < m, o <= n

Could you recheck that?

Re: All test case satisfy the constraints.

Re: Re: I did some additional tests and I have assertion failure on:
assert(0 < o && o <= n);

Last edit: 2017-02-23 11:01:06
vivek_singhvi: 2017-02-21 08:55:57

TLE with O(n) approach any suggestion

Re: Try DP :)

Last edit: 2017-02-21 15:13:56
marcelljason06: 2017-02-16 15:11:54

are you sure with all of your testcases? please check again.

Re: I had found and fixed a broken test case. Rejudged :)

edit : Thankyou :)

Last edit: 2017-02-17 01:22:01

Added by:Lucas
Date:2017-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All