3 Năm Đu Journey (Ham Hố)
Start of Real
Eme ngoài việc học hành không được chăm chỉ lắm ra thì cậu còn rất ham vui. Cậu thích đến những sự kiện âm nhạc rồi hú hét nhảy nhót theo nhịp của bàn DJ. Vì vậy, ba năm ở KC là ba năm cậu tham gia Journey - sự kiện chào học sinh mới của trường.
End of Real
Sự kiện không chỉ có những tiết mục văn nghệ, mà có cả những quầy đồ ăn, chụp ảnh hay minigame. Năm đó, Journey có \(N\) quầy vui chơi, mỗi quầy được đánh số từ 1 đến \(N\). Các bạn học sinh khi tham gia đều được dán trên tay một miếng dán điện tử, và mỗi bạn sẽ được đánh dấu bởi một mã số. Các bạn được đánh số từ 1, tăng dần theo thời gian tham dự sự kiện. Mỗi khi một bạn tham gia, hay một bạn di chuyển từ quầy này sang quầy khác, hệ thống đều ghi lại nhật kí. Các dòng trong nhật kí được sắp xếp theo thứ tự thời gian, tức là hoạt động này xảy ra trước thì ghi trước. Có hai loại hoạt động được ghi nhật kí:
NEW x- một bạn mới đến và bạn đó tới quầy thứ \(x\).MOVE k x- bạn có mã số \(k\) di chuyển sang quầy thứ \(x\).LEAVE k- bạn có mã số \(k\) rời sự kiện.
Nhật kí đã ghi được \(Q\) dòng. BTC đang làm một thống kê, và muốn biết, sau mỗi dòng nhật kí, quầy đông nhất sự kiện đang có bao nhiêu bạn.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên \(N, Q \ (1\le N\le 10^5; 1\le Q \le 10^5)\);
- \(Q\) dòng tiếp theo, mỗi dòng chứa một thông tin về hoạt động được lưu trong nhật kí \((1\le x\le N; k\) thuộc tập hợp chứa mã số của những bạn đang tham gia sự kiện vào thời điểm ghi nhật kí\()\).
Kết quả
- In trên \(Q\) dòng, mỗi dòng là kết quả sau mỗi dòng nhật kí.
Chấm điểm
- Subtask 1 (40%): \(N,Q \le 10^3\).
- Subtask 2 (30%): \(Q \le 10^3\).
- Subtask 3 (30%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
3 6
NEW 1
NEW 1
MOVE 1 2
NEW 3
MOVE 2 3
LEAVE 2
output
1
2
1
1
2
1
Comments