Khách sạn (Hotel)

Nguồn: POJ

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

Đề bài

Một khách sạn có $N$ phòng liên tiếp, đánh số từ $1$ đến $N$, ban đầu đều trống. Có $M$ yêu cầu:

• 1 D: một đoàn cần đúng $D$ phòng liên tiếp. Nếu có thể, hãy chọn đoạn phòng trống có vị trí bắt đầu nhỏ nhất, in vị trí bắt đầu rồi đánh dấu toàn bộ $D$ phòng là đã có khách. Nếu không có đoạn phù hợp, in 0.
• 2 X D: trả phòng cho toàn bộ đoạn $X,X+1,\ldots,X+D-1$. Một số phòng trong đoạn có thể vốn đã trống.

Input

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

$M$ dòng tiếp theo mô tả các yêu cầu như trên.

Output

Với mỗi yêu cầu loại 1, in vị trí bắt đầu được chọn hoặc 0.

Subtask

• Subtask 1 — 20%: $1\le N,M\le50$.
• Subtask 2 — 30%: $1\le N,M\le5000$.
• Subtask 3 — 50%: $1\le N\le50000$, $1\le M<50000$, $1\le D\le N$ và truy vấn trả phòng luôn có đoạn hợp lệ trong $[1,N]$.

Ví dụ

Input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

Output

1
4
7
0
5

Giải thích

Ba đoàn đầu lần lượt chiếm các đoạn bắt đầu tại $1,4,7$. Đoàn thứ tư không còn đủ ba phòng liên tiếp nên nhận $0$. Sau khi trả phòng $5..9$, đoàn cần sáu phòng bắt đầu tại $5$.