Để kiếm thêm tiền, những con bò đã mở một nhà hàng chuyên phục vụ sữa lắc trong chuồng của chúng. Nhà hàng có \(N\) chỗ ngồi (\(1 \le N \le 500\,000\)) xếp thành một hàng. Ban đầu, tất cả các chỗ đều trống.

Trong ngày, có \(M\) sự kiện khác nhau xảy ra tuần tự tại nhà hàng (\(1 \le M \le 300\,000\)). Có hai loại sự kiện:

1. Một đoàn khách có \(p\) thành viên đến (\(1 \le p \le N\)). Bessie muốn xếp đoàn khách vào một khối liên tiếp gồm \(p\) chỗ ngồi trống. Nếu có thể, cô xếp họ vào vị trí thấp nhất có thể trong dãy ghế. Nếu không thể, đoàn khách bị từ chối.
2. Một đoạn \([a,b]\) được cho trước (\(1 \le a \le b \le N\)), và tất cả mọi người ngồi trong đoạn ghế đó rời đi.

Hãy giúp Bessie đếm tổng số đoàn khách bị từ chối trong suốt cả ngày.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, mỗi dòng mô tả một sự kiện. Dòng có dạng A p (nghĩa là một đoàn khách có \(p\) thành viên đến) hoặc L a b (nghĩa là tất cả những con bò trong đoạn ghế \([a,b]\) rời đi).

Dữ liệu ra

In ra số đoàn khách bị từ chối.

Ví dụ

10 4
A 6
L 2 4
A 5
A 2

1

Nguồn

USACO 2013 January Contest, Gold — Problem 3: Seating

Tác giả đề: Travis Hance, 2012.