Cut the Rope

maruf_0011 SUST Inter University Pro...
Limits 10s, 512 MB

Fahim is a rope seller. He has a special tool for cutting ropes. But recently this tool is behaving oddly. Everytime he tries to cut some rope, it cuts the rope at a random point from the starting point.

He doesn’t have enough money to repair the machine. As his friend, you need to find the kk-th smallest rope segment after cutting the rope few times with the machine.

Input

There will be several test cases.

The first line of the input contains the integer TT (0<T400 < T \le 40), the number of test cases.

Every test case starts with a value NN (1<N<10151 < N < 10^{15}), the length of the rope. And, QQ (1Q1051 ≤ Q ≤ 10^5).

The next QQ lines each contain a character ('C' or 'F') and an integer XX (1X10151 ≤ X ≤ 10^{15}). Each line represents a query.

If the line starts with 'C', then the machine cuts the rope at position XX.

If the line starts with 'F' then find the length of the XX-th rope segment, after sorting the ropes by length.

Output

For every test case, print "Case X:" (where X is the case number) as the first line. Then, for every query that starts with 'F' print the length of the desired rope in a single line.

Sample

InputOutput
1
10 5
C 4
F 1
F 2
C 9
F 1
Case 1:
4
6
1

Submit

Login to submit.

Contributors

Statistics

70% Solution Ratio
DiversityEarliest, Aug '17
abiramee.731829Fastest, 0.0s
abiramee.731829Lightest, 8.0 kB
mahdi.hasnatShortest, 855B
Toph uses cookies. By continuing you agree to our Cookie Policy.