Bật tắt đèn (Light Switching)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ bóng đèn ban đầu đều tắt. Hỗ trợ đảo trạng thái cả đoạn và đếm số đèn đang bật trên đoạn.

Input

Dòng đầu chứa $n,m$. Mỗi trong $m$ dòng tiếp theo có dạng op l r.

• 0 l r: đảo trạng thái mọi đèn từ $l$ đến $r$.
• 1 l r: hỏi có bao nhiêu đèn đang bật từ $l$ đến $r$.

Output

In một dòng cho mỗi truy vấn loại 1.

Subtask

• 20 điểm: $2\le n\le50$, $m\le50$.
• 30 điểm: $n,m\le5000$.
• 50 điểm: $2\le n\le10^5$, $1\le m\le10^5$, $1\le l\le r\le n$.

Ví dụ

Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

Output

1
2

Giải thích

Sau hai lần đảo, trạng thái là 1 0 1 1, nên đoạn $[2,3]$ có một đèn bật. Đảo $[2,4]$ lần nữa thu được 1 1 0 0, nên toàn dãy có hai đèn bật.