🎶Nừ ná na na a Bộ ơi 🎵

Bộ PC có \(N\) ứng dụng trên điện thoại. Bạn cần xử lý \(Q\) sự kiện xảy ra theo thứ tự, thuộc một trong ba loại sau:

1. Loại 1 (dạng 1 x): Ứng dụng \(x\) tạo ra một thông báo mới (thông báo này ban đầu ở trạng thái chưa đọc).
2. Loại 2 (dạng 2 x): Bộ PC đọc toàn bộ thông báo của ứng dụng \(x\). Tất cả thông báo (cũ và mới) của ứng dụng \(x\) được đánh dấu là "đã đọc".
3. Loại 3 (dạng 3 t): Bộ PC đọc \(t\) thông báo đầu tiên được tạo ra (tính theo thứ tự thời gian của các sự kiện loại 1). \(t\) thông báo này được đánh dấu là "đã đọc" (ngay cả khi chúng đã được đọc trước đó).

Ban đầu, không có thông báo nào. Hãy tính và in ra tổng số lượng thông báo chưa đọc sau mỗi sự kiện.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 300000\)).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một sự kiện.
  • Nếu sự kiện loại 1 hoặc 2, dòng chứa 2 số \(type\) và \(x\) (\(type \in \{1, 2\}\), \(1 \le x \le N\)).
  • Nếu sự kiện loại 3, dòng chứa 2 số \(type\) và \(t\) (\(type = 3\), \(1 \le t \le Q\)). Đảm bảo \(t\) không vượt quá tổng số sự kiện loại 1 đã xảy ra tính đến thời điểm đó.

Output

• In ra \(Q\) dòng, mỗi dòng là một số nguyên - số lượng thông báo chưa đọc sau khi sự kiện tương ứng xảy ra.

Examples

3 4
1 3
1 1
1 2
2 3

1
2
3
2

4 6
1 2
1 4
1 2
3 3
1 3
1 3

1
2
3
0
1
2