Bình hoa và hoa (Vases and Flowers)

Nguồn: HDU

Phiên bản: Phước Hưng OJ Extended

Đề bài

Alice có $N$ bình hoa, đánh số từ $0$ đến $N-1$, ban đầu đều trống. Mỗi bình chứa nhiều nhất một bông hoa. Có $M$ thao tác:

• 1 A F: Alice nhận $F$ bông hoa. Bắt đầu từ bình $A$, cô đi sang phải. Gặp bình trống thì đặt một bông vào đó, gặp bình đã có hoa thì bỏ qua. Dừng khi hết hoa hoặc đã xét bình $N-1$; hoa còn thừa bị bỏ đi. Nếu đặt được ít nhất một bông, in vị trí của bình nhận bông đầu tiên và bông cuối cùng. Nếu không đặt được bông nào, in Can not put any one..
• 2 A B: dọn sạch tất cả bình từ $A$ đến $B$ và in số bông hoa bị bỏ đi.

Input

Dòng đầu chứa $N,M$.

$M$ dòng tiếp theo chứa ba số nguyên mô tả một thao tác.

Output

Với thao tác loại 1, in hai vị trí đầu/cuối hoặc chuỗi Can not put any one..

Với thao tác loại 2, in số bông hoa bị dọn bỏ.

Subtask

• 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$, và với loại 2 có $A\le B\le N-1$.

Ví dụ

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.

Giải thích

Lần đặt đầu bắt đầu ở bình $3$ và dùng các bình trống đến $7$. Khi dọn $[4,5]$ có hai bông bị bỏ. Ở thao tác cuối, từ bình $8$ trở đi không còn bình trống nên in thông báo.