 Server Time: Thu Feb 20, 2020 2:54 am
 Welcome ( logout ) 1135 - Count the Multiples of 3  PDF (English) Statistics Forum
 Time Limit: 3 second(s) Memory Limit: 64 MB

You have an array with n elements which is indexed from 0 to n - 1. Initially all elements are zero. Now you have to deal with two types of operations

1.      Increase the numbers between indices i and j (inclusive) by 1. This is represented by the command '0 i j'.

2.      Answer how many numbers between indices i and j (inclusive) are divisible by 3. This is represented by the command '1 i j'.

# Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case starts with a line containing two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form '0 i j' or '1 i j' where i, j are integers and 0 ≤ i ≤ j < n.

# Output

For each case, print the case number first. Then for each query in the form '1 i j', print the desired result.

1

10 9

0 0 9

0 3 7

0 1 4

1 1 7

0 2 2

1 2 4

1 8 8

0 5 8

1 6 9

Case 1:

2

3

0

2

# Note

Dataset is huge, use faster i/o methods.

Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan