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.
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.
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.
1 10 5 C 4 F 1 F 2 C 9 F 1
Case 1: 4 6 1
Login to submit