힘의 결합

빛이 섬 곳곳을 비추기 시작하자, 각 집에 깃든 힘의 흐름이 달라지기 시작했다. 시간에 따라 힘은 이리저리 옮겨졌고, 그 흔적은 조용히 기록되었다.

사람들은 힘의 흐름이 지나간 모든 순간을 되짚으며, 그 안에서 가장 강했던 결합의 순간을 찾아내고자 했다.

그들이 나눈 힘의 흐름을 따라가고, 잃어버린 기록을 되찾아라.

섬의 마을에는 $N$개의 집이 일렬로 놓여 있으며, 집은 왼쪽부터 차례대로 $1$부터 $N$까지의 번호가 붙어 있다.

$0$일째에 집 $i$는 $a_i$만큼의 힘을 지니고 있었다.

시간이 지남에 따라 집들 사이에서 힘이 이동하는 현상이 $M$일 동안 일어났다. 구체적으로, $i$번째 날에는 $x_i$번 마을의 힘이 $v_i$만큼 증가하고, $x_i+1$번 마을의 힘이 $v_i$만큼 감소했다. ($v_i$는 음수일 수도 있다.)

사람들은 시간에 따른 힘의 변화를 격자에 기록했다. 예를 들어, $N=4$, $M=5$, $a=[3,-2,2,-2]$, $x=[3,1,2,1,2]$, $v=[-4,-2,3,2,-4]$인 경우, 각 집의 힘은 시간에 따라 아래와 같이 변한다. 이때 각 행은 날의 번호에 대응되고, 각 열은 집의 번호에 대응된다.

힘의 변화가 일어남에 따라, 몇몇 사람들은 집의 결속력을 강화하고 힘을 분배할 수 있도록 결합을 형성하고자 하였다. 결합이 형성되는 과정은 다음과 같다.

• 결합을 형성할 날짜 $t$와 결합을 이끌 집의 번호 $x$를 정한다. $(0\le t\le M,1\le x\le N)$
• $x$번 집을 포함하는 연속한 집의 구간 $[l,r]$을 고른다. $(1\le l\le x\le r\le N)$
• 결합의 힘은 결합을 이루는 집의 힘의 합과 같다. 단, 각 집의 힘은 결합을 형성한 $t$번째 날의 힘을 기준으로 한다.
  • 이때, $P_{tx}$를 $t$와 $x$의 값이 고정되었을 때 만들 수 있는 결합의 힘의 최댓값으로 정의하자.

사람들은 결합을 계획하기 위해 여러 시간대와 여러 집에 대해 가능한 결합의 힘을 비교하고자 하였다. 이 과정에서 $Q$가지의 질문이 등장했는데, 그중 $i$번째 질문은 다음과 같다.

• $s_i\le t\le e_i$, $l_i\le x\le r_i$인 모든 $(t,x)$에 대해, $P_{tx}$의 합이 무엇인가?

결합을 만드는 다양한 가능성을 살펴보고, 각각의 계획이 얼마나 강한지 알아내어 보자.

첫 줄에는 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다.

둘째 줄에는 초기 집의 힘을 나타내는 $N$개의 정수 $a_1,a_2,\cdots ,a_N$이 공백으로 구분되어 주어진다.

이후 $M$개의 줄에 걸쳐, 힘의 이동에 관한 두 정수 $x_i$, $v_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 날에 $x_i$번 집의 힘이 $v_i$만큼 증가하고, $x_i+1$번 집의 힘이 $v_i$만큼 감소한다는 의미이다.

이후 $Q$개의 줄에 걸쳐, 각 질문을 나타내는 네 정수 $s_i,e_i,l_i,r_i$가 공백으로 구분되어 주어진다.

$Q$가지 질문 각각에 대해 그 답을 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

• $2\le N\le 10^5$
• $1\le M\le 10^5$
• $1\le Q\le 10^5$
• $-10^9\le a_i\le 10^9$ $(1\le i\le N)$
• $1\le x_i<N$ $(1\le i\le M)$
• $-10^9\le v_i\le 10^9$ $(1\le i\le M)$
• $0\le s_i\le e_i\le M$ $(1\le i\le Q)$
• $1\le l_i\le r_i\le N$ $(1\le i\le Q)$