Simple Difference Array

Problem Description

You are given an array $A$ of length $n$. Perform the following operations $m$ times:

Select an interval $[l, r]$ and add the integer $x$ to every number in that interval.

After all operations are done, answer $k$ queries:

Each query gives an interval $[l, r]$ and asks for the sum of all numbers in that interval.

Input Format

The first line contains three positive integers $n, m, k$.

The next line contains $n$ numbers, the array $A$.

The next $m$ lines each contain three integers $l, r, x$.

The next $k$ lines each contain two integers $l, r$.

Output Format

Output $k$ lines, each containing one number — the sum for the corresponding query.

Sample Input

10 1 1
1 2 3 4 5 6 7 8 9 10
5 8 1
8 9

Sample Output

18

Constraints

For all data: $1 \leq n \leq 2 \times 10^5$, $1 \leq m, k \leq 10^5$, $|x| \leq 10^5$.