#1311 · BÃI ĐẬU XE HUTECH

Bãi đậu xe máy của HUTECH ở Thu Duc Campus gồm N vị trí được sắp xếp theo một đường thẳng và đánh số từ 1 đến N và bãi xe tiếp nhận M xe ra và vào mỗi ngày.

Do số lượng xe ra vào bãi xe quá lớn, vì vậy hãy giúp nhân viên bãi xe tìm ra vị trí đậu xe sao cho thuận tiện nhất.

Giả sử ban đầu bãi xe trống, khi có 1 xe vào, nhân viên có nhiệm vụ tìm ra 1 vị trí phù hợp cho xe đó đậu với yêu cầu vị trí đậu xe phải cách xa nhất những vị trí đã có xe đã đậu. Nếu tồn tại nhiều vị trí thì sẽ chọn vị trí có số nhỏ nhất. Biết rằng:

• Khoảng cách giữa 2 vị trí i và j được tính theo công thức sau: D_{ij} = 4 \times |i - j|
• Các xe được đánh số từ 1 đến 10^6 và không có xe nào đi ra khi chưa đi vào hoặc không có xe nào đi vào mà đang ở trong bãi.
• Đảm bảo luôn còn chỗ cho các xe mới vào.

• Dòng đầu tiên gồm 2 số nguyên N, M (1 \leq N, M \leq 10^5)
• M dòng tiếp theo gồm 2 số nguyên T, X (1 \leq T \leq 2; 1 \leq X \leq 10^6) với T = 1 thì xe có số thứ tự là X đi vào bãi gửi xe, T = 2 thì xe có số thứ tự là X đi ra khỏi bãi gửi xe.

Với mỗi truy vấn T = 1, xuất vị trí mà một xe vào sẽ đậu.

• Subtask 1 (50% số test): 1 \leq N \leq M \leq 1000
• Subtask 2 (50% số test): Không có ràng buộc gì thêm