Gats and the Milk Trail

Time limit: 2000 msMemory limit: 256 MB

Along a corridor there are $N$ bowls, indexed from $1$ to $N$ . Bowl $i$ currently contains $A_i$ drops of milk.

Two kinds of events happen. Griffithm may pour milk into one bowl, or Gats may choose a segment from bowl $l$ to bowl $r$ and a thirst value $x$ .

During one drinking event, Gats examines bowls $l,l+1,\ldots,r$ in increasing order. Empty bowls are ignored. If he reaches a bowl containing $y > 0$ drops and still needs $z$ drops to reach his thirst value , he drinks drops from that bowl. Every drop he drinks is removed from its bowl. If he has drunk drops, or if there are no more bowls in the chosen segment, the event ends.

For every drinking event, report the number of drops Gats actually drinks.

Input

The first line contains two integers $N$ and $Q$ ( $1 \le N,Q \le 2 \times 10^5$ ), the number of bowls and operations.

Output

For each operation whose first token is D, in the order those operations appear, print one line containing one integer: the number of drops Gats actually drinks during that operation. If this number is $0$ , print $0$ . If there are no operations whose first token is D, print no output.

Samples

Sample 1

Input

Output

Initially the bowls contain $[3,0,4,2,1]$ . The first drinking event is on bowls $2$ through $4$ with $x=5$ ; Gats skips bowl , drinks drops from bowl , and drinks drop from bowl . After all operations are applied in order, the printed amounts are , , , , and .

Gats and the Milk Trail

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2