### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

The problem can be solved using segment trees. Every node of the tree stores the following data :

- tree0[k] : In the range [low…high] covered by this node, how many numbers are divisible by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
- tree1[k] : In the range [low…high] covered by this node, how many numbers leave a remainder of 1 when divided by 3 considering just additions performed on numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2
- add[k] : What is the quantity which is added to all numbers totally inside this range and not considering additions performed on ranges which are a subrange of the range covered at node k/2