Statement

A hospital has $m$ doctors, all initially idle. The system receives $q$ commands in nondecreasing time order. Each patient has a unique identifier, a priority, and a treatment duration. Larger priority is served first; ties are broken by earlier arrival time and then by smaller identifier.

Before processing a command at time $t$, all treatments ending no later than $t$ are processed. When a doctor finishes at time $x$, the doctor immediately starts treating the best patient currently waiting, if one exists. Then the current command is executed. Whenever both an idle doctor and a waiting patient exist, treatment starts immediately.

Commands are A t id p d (arrival), C t id (cancel only if still waiting), and Q t (print the number waiting, number under treatment, and the identifier at the head of the waiting queue, or 0 if it is empty).

Input

The first line contains $m,q$ ($1 \le m,q \le 200000$). The next $q$ lines contain commands in nondecreasing time order. Arrival identifiers are distinct and lie in $[1,q]$. All priorities and durations are positive.

Output

For every query, print the waiting count, treating count, and current waiting-queue head identifier.

Samples

Sample 1

Input:

1 8
A 0 1 5 4
A 1 2 9 3
Q 1
C 2 2
Q 2
A 4 3 7 2
Q 4
Q 6

Output:

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