Công Tắc Chiếu Sáng Hầm Hải Vân

Mô tả

Hầm đường bộ Hải Vân dài đặc biệt, nên hệ thống chiếu sáng được chia thành nhiều cụm đèn LED. Mỗi cụm có một công tắc độc lập, trạng thái ban đầu của toàn bộ các cụm đều đang tắt.

Kỹ sư vận hành có ba thao tác điều khiển trên một đoạn liên tiếp các cụm đèn từ vị trí l đến vị trí r:

• Bật: đổi trạng thái tất cả đèn trong đoạn thành bật.
• Tắt: đổi trạng thái tất cả đèn trong đoạn thành tắt.
• Xoá: đảo trạng thái tất cả đèn trong đoạn (đang bật thành tắt và ngược lại).

Sau khi thực hiện một chuỗi thao tác, bạn cần cho biết tổng cộng có bao nhiêu cụm đèn đang ở trạng thái bật.

Đầu vào

• Dòng đầu chứa hai số nguyên n và q (1 ≤ n ≤ 10^4, 1 ≤ q ≤ 10^4), lần lượt là số cụm đèn và số thao tác.
• q dòng tiếp theo, mỗi dòng chứa một xâu type và hai số nguyên l, r (1 ≤ l ≤ r ≤ n), trong đó type là một trong ba giá trị: ON, OFF, TOGGLE.

Đầu ra

• In ra một số nguyên duy nhất là số cụm đèn đang bật sau khi thực hiện tất cả thao tác.

Ràng buộc

• 1 ≤ n ≤ 10^4
• 1 ≤ q ≤ 10^4
• 1 ≤ l ≤ r ≤ n
• Subtask 1 (40% điểm): n, q ≤ 100.
• Subtask 2 (60% điểm): không có ràng buộc thêm.

Ví dụ

Input:

5 3 ON 1 3 TOGGLE 2 4 OFF 3 5

Output:

1

Giải thích:

• Ban đầu 5 đèn đều tắt: [0, 0, 0, 0, 0].
• ON 1 3: bật đèn 1-3 → [1, 1, 1, 0, 0].
• TOGGLE 2 4: đảo đèn 2-4 → [1, 0, 0, 1, 0].
• OFF 3 5: tắt đèn 3-5 → [1, 0, 0, 0, 0].
• Kết quả có đúng 1 đèn sáng.