ModuloSum

Task

The following problem was passed down through the generations in the InfO(1)Cup Kingdom - can you solve it?

You are given a sequence $A_0, \dots, A_{N-1}$ of $N$ non-negative integers, and $Q$ queries of the form $(L_i, R_i, M_i)$ for $i = 0, \dots, Q-1$. For each query, compute:

For example, if $L = 2$, $R = 3$, $M = 5$, $A_2 = 3$, $A_3 = 4$, then the answer is $(3 \text{mod} 5) + (4 \text{mod} 5) = 7$.

Implementation details

You should implement the following function:

std::vector<long long> solve(
	int N, int Q,
	std::vector<int> A,
	std::vector<int> L,
	std::vector<int> R,
	std::vector<int> M
);

This function should return the answer for the given $Q$ instructions. It will only be called once per execution by the committee's grader. Note that the array $A$ is indexed from $0$ to $N-1$, and the arrays $L$, $R$, $M$ are indexed from $0$ to $Q - 1$.

Remember to include the header modulosum.h! Also, remember that you should not implement the main function, only solve.

Sample grader behaviour

The sample grader will read $N$, $Q$, the array $A$, then $Q$ triplets $(L_i, R_i, M_i)$. It will then call $\text{solve}(N, Q, A, L, R, M)$, and output the returned values to standard output, one on a line. The input/output files below work for this grader.

Constraints and clarifications

• $1 \leq N \leq 100 \ 000$;
• $1 \leq Q \leq 100 \ 000$;
• $0 \leq L_i \leq R_i \lt N$;
• $1 \leq M_i \leq 1 \ 000 \ 000 \ 000$;
• $1 \leq A_i \leq 300 \ 000$.

Example 1

stdin

5 4
5 1 4 2 3
0 2 4
1 4 3
2 3 3
0 4 10

stdout

2
4
3
15

Explanation

In the first question, $(5$ mod $4) + (1$ mod $4) + (4$ mod $4) = 1 + 1 + 0 = 2$.
In the second question, $(1$ mod $3) + (4$ mod $3) + (2$ mod $3) + (3$ mod $3) = 1 + 1 + 2 + 0 = 4$.
In the third question, $(4$ mod $3) + (2$ mod $3) = 1 + 2 = 3$.
In the fourth question, $(5$ mod $10) + (1$ mod $10) + (4$ mod $10) + (2$ mod $10) + (3$ mod $10) = 5 + 1 + 4 + 2 + 3 = 15$.