Multiples Of 3
medium
There are N numbers(indexed from 1 to N) initially all are 0. You have to perform Q operations of two types: 1. 1 A B: increase all numbers in range from index A to B by 1. 2. 2 A B: count how many numbers in range from index A to B are divisible by 3.
Constraints
1. 1 <= N <= 10^5 2. 1 <= A <= B <= N
Format
Input
First line contains one integer N Second line contains one integer Q following Q lines contains queries of format either : 1 A B or 2 A B
Output
for all query of type 2 A B print in seperate lines count of numbers.
Example
Sample Input
4
7
2 1 4
1 2 3
1 2 4
2 1 1
1 1 4
2 4 4
2 1 4
Sample Output
4
1
0
2