파이몬의 세그먼트 트리

파이몬은 방금 지속성 세그먼트 트리를 배웠고, 바로 연습해 보려 한다. 그래서 루미네는 시작하기 좋은 쉬운 문제를 하나 준다.

길이가 $n$인 수열 $a_1, a_2, \cdots, a_n$이 주어진다. 루미네는 이 수열에 $m$번의 변경을 적용한다. $i$번째 변경은 세 정수 $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$)와 $x_i$로 주어지며, $l_i \le k \le r_i$인 모든 $k$에 대해 $a_k$를 $a_k + x_i$로 바꾼다.

$a_{i,t}$를 $t$번째 변경 직후의 $a_i$ 값이라고 하자. 이렇게 하면 $a_i$의 과거 값을 모두 추적할 수 있다. $t$번째 변경이 $a_i$를 건드리지 않았다면 $a_{i,t}$는 $a_{i,t-1}$과 같다. 완전성을 위해 $a_{i,0}$은 $a_i$의 초기 값으로 정의한다.

모든 변경이 끝난 뒤, 루미네는 파이몬에게 $q$개의 질의를 준다. $k$번째 질의는 네 정수 $l_k$, $r_k$, $x_k$, $y_k$로 주어지며, 다음 값을 구해야 한다.

$\sum_{i=l_k}^{r_k}\sum_{j=x_k}^{y_k} a_{i,j}^2$

모든 질의의 답을 구하라. 답이 매우 클 수 있으므로 각 답은 $10^9 + 7$로 나눈 나머지로 출력한다.

첫 줄에는 세 정수 $n$, $m$, $q$ ($1 \le n, m, q \le 5 \times 10^4$)가 주어진다. 각각 수열의 길이, 변경의 개수, 질의의 개수이다.

둘째 줄에는 초기 수열의 정수 $n$개 $a_1, a_2, \cdots, a_n$ ($|a_i| < 10^9 + 7$)이 주어진다.

다음 $m$개 줄에는 각각 변경을 나타내는 $l_i$, $r_i$, $x_i$ ($1 \le l_i \le r_i \le n$, $|x_i| < 10^9 + 7$)가 주어진다.

다음 $q$개 줄에는 각각 질의를 나타내는 $l_k$, $r_k$, $x_k$, $y_k$ ($1 \le l_k \le r_k \le n$, $0 \le x_k \le y_k \le m$)가 주어진다.

입력 파일에는 테스트 케이스가 하나만 있다.

각 질의마다 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.