Vases and Flowers

Source: HDU

Version: Phuoc Hung OJ Extended

Problem Statement

Alice has $N$ vases numbered $0$ through $N-1$, initially empty. Each vase can contain at most one flower. Process $M$ operations:

• 1 A F: Alice receives $F$ flowers and scans vases from $A$ to the right. She puts a flower into every empty vase encountered, skips occupied vases, and stops when no flower remains or vase $N-1$ has been processed. Extra flowers are discarded. If at least one flower is placed, print the positions of the first and last vases receiving a flower. If none can be placed, print Can not put any one..
• 2 A B: clean all vases from $A$ through $B$ and print the number of flowers discarded.

Input

The first line contains $N,M$.

The next $M$ lines each contain three integers describing one operation.

Output

For type 1, print the first and last positions, or Can not put any one..

For type 2, print the number of discarded flowers.

Subtasks

• Subtask 1 — 20%: $2\le N,M\le50$.
• Subtask 2 — 30%: $2\le N,M\le5000$.
• Subtask 3 — 50%: $2\le N,M<50001$, $0\le A\le N-1$, and type 2 satisfies $A\le B\le N-1$.

Examples

Input

10 5
1 3 5
2 4 5
1 1 8
2 3 6
1 8 8

Output

3 7
2
1 9
4
Can not put any one.

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.