Cut the Rope
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.
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.
1 < N < 1015
1 ≤ Q ≤ 105
1 ≤ X ≤ 1015
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.
1 10 5 C 4 F 1 F 2 C 9 F 1
Case 1: 4 6 1