Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Cut the Rope

Limits: 5s, 512 MB

Bokkor is a rope seller. He has a special tool for cutting rope. But recently this tool is behaving weirdly. When he tries to cut the rope, it puts the cut in a random position of the rope from the starting position. He doesn’t have enough money to repair the machine. As his friend, you need to find the kth smallest rope segment after cutting the rope few times with the machine.

Input

There will be several test cases. First line of the input contains the number T < 40 (Number of test cases).

Every test case start with a value N (Length of the rope) and Q (number of query). Next Q lines contain a character (‘C’ or ‘F’) and an integer ‘X’. If the query starts with ‘C’, then the machine cut the rope at position X. If it starts with ‘F’ then find the Length of the Xth rope segment, after sorting the ropes by length. Queries will always be valid.

Constraints:
1 < N < 1015
1 ≤ Q ≤ 105
1 ≤ X ≤ 1015

Output

For every test case, the first line contains “Case X:”. X is the case number.
For every query starts with F. you need to print the length of the desired rope in a single line.

Samples

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

Discussion
Submit

Login to submit