# 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

**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 **k ^{th}** 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 **X ^{th}** rope segment, after sorting the ropes by length. Queries will always be valid.

**Constraints:****1 < N < 10 ^{15}**

**1 ≤ Q ≤ 10**

^{5}**1 ≤ X ≤ 10**

^{15}#### 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

Input | Output |
---|---|

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

Login to submit