Multiples of 3

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

An array of $n$ values starts at zero. Each update increments a range; each query counts values divisible by 3.

Input

The first line contains $n,q$. Each following line is type a b, using zero-based indices.

• 0 a b: increment every value in $[a,b]$ by 1.
• 1 a b: count values in $[a,b]$ that are divisible by 3.

Output

Print the answer to each type 1 query.

Subtasks

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

Examples

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

Explanation

Initially all four values are 0, so the first answer is 4. Range increments rotate residues modulo 3; the remaining query answers are 1, 0, and 2.