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

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 kth 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 T (T < 40), the number of test cases.

Every test case starts with a value N (1 < N < 1015), the length of the rope. And, Q (1 ≤ Q ≤ 105).

The next Q lines each contain a character (‘C’ or ‘F’) and an integer X (1 ≤ X ≤ 1015). Each line represents a query.

If the line starts with ‘C’, then the machine cuts the rope at position X.

If the line starts with ‘F’ then find the length of the Xth 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.

Samples

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

Author
Discussion
Submit

Login to submit