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.
Input Format
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 Format
for all query of type 2 A B print in seperate lines count of numbers.
Constraints
1. 1 <= N <= 10^5 2. 1 <= A <= B <= N
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
4 7 2 1 4 1 2 3 1 2 4 2 1 1 1 1 4 2 4 4 2 1 4
Output
4 1 0 2