Divisible by 3 - MarisaOJ: Marisa Online Judge

Divisible by 3

Time limit: 1000 ms
Memory limit: 256 MB
You are given array A of n integers. There are q queries of the either form: - 1lr: increasing Al,Al+1,...,Ar by 1. - 2lr: find the number of number divisible by 3 in subarray Al,Al+1,...,Ar. ### Input - The first line contains 2 integers n,q. - The second line contains n integers Ai. - The next q lines, each line contains 3 integers, a query. ### Output - Print the answer for each query of type 2. ### Constraints - 1≤n,q≤105. - 1≤l,r≤n. - 1≤Ai≤109. ### Example Input: 5312232224115235 Output: 12