The parking lot in the center of the capital has N parking spaces. You are asked to develop a program to write the parking log of the lot. The program is required to record such two operations which may happen in the lot:

A: A motorcade with Mi cars applies for Mi parking spaces in a row, namely, continuous spaces[S_{i}; S_{i} + M_{i }− 1]. A special constraint is that the number of free spaces between the coming motorcade and the last car parking before Si, should not be larger than Li. Note that, this constraint has no eﬀect if there is no car before Si. What’s more, the number of free spaces between the coming motorcade and the ﬁrst car parking after S_{i} + M_{i} − 1 should not be larger than R_{i}. Also, you should ignore this constraint when S_{i}+M_{i}−1 is last occupied space. The space

with the smallest Si is selected when there are several candidate start places. The motorcade will leave if there are no spaces satisfying the conditions. After one motorcade is parked, its parking limits L_{i} and R_{i} can be ignored when ﬁnding parking places for later coming motorcades. Your task is to ﬁnd the S_{i}, and return it as result.

B. The kth motorcade counted from left to right leaves the lot. Ignore this operation if there are

no more than k motorcades in the parking lot.

In the very beginning, the spaces in the lot are all free.

## 1006: 【2012四川省热身赛】Problem D. Parking Log

Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0

[Submit][Status][Web Board]

## Description

## Input

First line of the input is a single integer T(T ≤ 10), indicates there are T test cases.

For each test case, the ﬁrst line is two integers N(1 ≤ N ≤ 5 · 10^{4}) Q(1 ≤ Q ≤ 10^{5}), representingthe size of the lot and the number of operations.

The following Q lines give the operations, in which lines with one char and three integers as “A M L R” (0 < M; L;R ≤ 5 · 10^{4}) representing operations of type A, and lines with one char and a single number are of type B.

## Output

For each test case, you should output “Case #t:” ﬁrst. After that, your program should output

the result place for each operation A, −1 if no place available.

## Sample Input

```
2
90 5
A 77 2 2
B 3
B 1
A 53 2 3
A 7 3 3
7 15
A 3 1 1
A 1 1 1
B 1
A 1 1 1
A 1 1 1
B 2
A 2 1 1
A 1 1 1
A 2 1 1
A 1 1 1
B 4
B 3
B 2
A 1 1 1
A 2 1 1
```

## Sample Output

```
Case #1:
1
1
54
Case #2:
1
4
2
1
2
5
6
-1
-1
3
```