Bội số của 3 (Multiples of 3)

Nguồn: SPOJ

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

Đề bài

Dãy gồm $n$ số ban đầu đều bằng 0. Mỗi cập nhật tăng cả đoạn thêm 1; mỗi truy vấn đếm phần tử chia hết cho 3.

Input

Dòng đầu chứa $n,q$. Mỗi dòng tiếp theo là type a b. Chỉ số bắt đầu từ 0.

• 0 a b: tăng mọi phần tử trong $[a,b]$ thêm 1.
• 1 a b: đếm phần tử trong $[a,b]$ chia hết cho 3.

Output

In đáp án của từng truy vấn loại 1 trên một dòng.

Subtask

• 20 điểm: $n,q\le50$.
• 30 điểm: $n,q\le5000$.
• 50 điểm: $1\le n,q\le10^5$, $0\le a\le b<n$.

Ví dụ

Input

4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3

Output

4
1
0
2

Giải thích

Ban đầu cả bốn số đều là 0 nên truy vấn đầu trả 4. Các phép tăng làm phần dư modulo 3 dịch vòng; sau toàn bộ thao tác, các truy vấn còn lại lần lượt cho 1, 0, 2.