Multiples of 3

There are n numbers a_0,a_1,...,a_{n-1}. Initially all are 0. You have to perform two types of operations:

1. Increase the numbers between indices a and b (inclusive) by 1. This is represented by the command "0 a b"

2. Answer how many numbers between indices a and b (inclusive) are divisible by 3. This is represented by the command "1 a b".

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 100000). Each of the next q lines are either of the form "0 a b" or "1 a b" as mentioned above. It is known that 0 ≤ a ≤ b ≤ n - 1.

Output

Print one line for each query of the form "1 a b" containing the required answer for the corresponding query.

Examples