Statement

A service desk has windows numbered $1$ through $n$, all initially free. Commands describe arriving teams, leaving seated teams, cancelling waiting teams, and queries. A team needs a consecutive block of windows.

Arrivals join a FIFO waiting queue. Whenever the queue head can be placed, it must be placed in the leftmost free consecutive block of the required length. Later teams may never bypass the head. After a leave or cancellation, placement is repeated immediately until the queue becomes empty or its head cannot fit.

Input

The first line contains $n,q$ ($1 \le n \le 100$, $1 \le q \le 200000$). Each following line is one command: A id k, L id, C id, or Q. Arrival identifiers are distinct and all requested block lengths are between $1$ and $n$.

Output

For every query, print the number of seated teams, waiting teams, and the identifier at the queue head, or 0 if the queue is empty.

Samples

Sample 1

Input:

6 10
A 1 4
A 2 3
Q
L 1
Q
A 3 4
C 3
Q
L 2
Q

Output:

1 1 2
1 0 0
1 0 0
0 0 0