Probably, you have already guessed that Benny really likes different types of queries.
Sometimes she goes for a walk with her friends, sometimes goes to the cinema. But all the time she goes somewhere she can not relax if homework was not made.
She kindly asks you to help her with her homework again.
In this problem you are given an array p consisting of n elements.
You have to answer m queries.
Each query has the following format: l r x. The answer to the query is r∑i=l(pimodx).
For each query output the answer in a single line.
Input format
The first line contains two integers n and m.
The second line contains n integers pi .
The next $m$ lines contain three integers each: l, r and x.
Constraints
1≤n,m≤2⋅105
0≤pi≤2⋅105
1≤l≤r≤n
1≤x≤2⋅105
Output format
For each query output the answer as a single integer.
Answer for each query:
- 2 + 0 + 2 + 2 + 0 + 2 + 2 + 1 + 0 = 11
- 0 + 9 + 19 + 4 + 2 + 10 + 18 + 5 + 8 = 75
- 6 + 2 + 2 + 9 + 5 + 5 + 4 + 3 = 36
- 0 + 2 + 2 + 2 + 1 + 1 + 1 = 9
- 2 + 2 + 0 + 2 + 3 + 1 + 0 + 0 + 3 = 13
