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