Giá treo áo

Phòng gửi đồ của một công ty có một giá treo áo gồm $n$ móc xếp thành một hàng ngang, đánh số từ $1$ đến $n$ từ trái sang phải. Đầu ngày làm việc giá treo hoàn toàn trống.

Trong ngày, các nhân viên lần lượt đến và ra về. Khi một nhân viên đến, anh ta treo áo lên một móc trống theo quy tắc sau:

1. Xét tất cả các đoạn móc trống liên tiếp (tối đại), chọn đoạn có độ dài lớn nhất.
2. Nếu có nhiều đoạn cùng độ dài lớn nhất, chọn đoạn nằm bên phải nhất.
3. Treo áo lên móc chính giữa đoạn đó. Nếu đoạn có số móc chẵn thì trong hai móc ở giữa, chọn móc bên phải.

Khi một nhân viên ra về, anh ta lấy đúng chiếc áo của mình, móc tương ứng trở lại trạng thái trống.

Thỉnh thoảng giám đốc muốn biết hiện có bao nhiêu chiếc áo đang được treo trên các móc từ $i$ đến $j$. Hãy trả lời tất cả các truy vấn đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ là số móc treo và số sự kiện.
• $q$ dòng tiếp theo mô tả các sự kiện theo thứ tự thời gian:
  • Dòng có dạng 0 i j là một truy vấn của giám đốc: đếm số áo đang treo trên các móc từ $i$ đến $j$.
  • Ngược lại, dòng chứa một số nguyên dương là mã của một nhân viên. Lần xuất hiện thứ lẻ của một mã ứng với việc nhân viên đó đến, lần xuất hiện thứ chẵn ứng với việc ra về.

Các nhân viên có mã đôi một khác nhau. Dữ liệu đảm bảo mỗi khi có nhân viên đến thì luôn còn ít nhất một móc trống, và có ít nhất một truy vấn của giám đốc.

Dữ liệu ra

Với mỗi truy vấn của giám đốc, in ra trên một dòng số áo đang treo trên các móc từ $i$ đến $j$.

Ràng buộc

• $1\le n\le {10}^9$
• $1\le q\le {10}^5$
• $1\le i\le j\le n$
• Mã nhân viên là số nguyên dương không vượt quá ${10}^9$

Ví dụ