Your preparations to visit Pluto have been going as planned, and you are ready to launch the rocket! All you need to do is calculate how much fuel is required. There are $$$n$$$ engines on the ship, and engine $$$i$$$ requires $$$f_{t, i}$$$ fuel at time $$$t$$$. You know the initial amount of fuel required, $$$f_{1, i}$$$, for each engine.
As time goes on, more and more fuel is required. Between times $$$t$$$ and $$$t + 1$$$, engines $$$l_t$$$ through $$$r_t$$$ require $$$d_t$$$ more fuel. In other words, the update is as follows: $$$$$$ f_{t + 1, i} = \begin{cases} f_{t, i} + d_t & \text{if $l_t \leq i \leq r_t$} \\ f_{t, i} & \text{otherwise} \end{cases} $$$$$$
As part of the fuel calculations, you want to answer $$$q$$$ queries about the fuel. Query asks for the total amount of fuel used by engines $$$ql_i$$$ through $$$qr_i$$$ between times $$$a_i$$$ and $$$b_i$$$. Can you answer each of the queries?
The first line of the input contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n, m, q \leq 2 \cdot 10^5$$$) — the number of engines, the number of updates, and the number of queries, respectively.
The next line contains $$$n$$$ space-separated integers $$$f_{1, 1}, f_{1, 2}, \dots, f_{1, n}$$$ ($$$0 \leq f_{1, i} \leq 10^5$$$) — the initial fuel required for each engine.
The next $$$m$$$ lines contain the $$$m$$$ updates. Each of these lines contains three integers $$$l_i$$$, $$$r_i$$$, and $$$d_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1 \leq d_i \leq 10^5$$$) — the leftmost engine updated at this time, the rightmost engine updated at this time, and how much more fuel each engine requires, respectively.
The next $$$q$$$ lines contain the $$$q$$$ queries. Each of these lines contains four integers $$$ql_i$$$, $$$qr_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1 \leq ql_i \leq qr_i \leq n$$$, $$$1 \leq a_i \leq b_i \leq m + 1$$$) — the leftmost engine queries, the rightmost engine queried, the earliest time queried, and the latest time queried, respectively.
Output $$$q$$$ integers representing the answer to each query in the order given in the input.
4 2 3 1 2 3 4 1 3 1 2 4 3 1 4 1 3 2 2 2 2 3 4 2 3
45 3 22
Note that the set of possible times that we can query includes time $$$m + 1$$$, which occurs after the final update.
For the sample input, the fuel required for each engine at each time is:
