삼각형의 부분합

그림과 같이 $\frac{N(N+1)}{2}$개의 구슬이 정삼각형 모양의 격자에 배열되어 있다. 이 격자는 $N$개의 층으로 이루어져 있다. 아래로 내려갈수록 층마다 놓인 구슬의 수가 늘어나서, 위에서 $i$번째 층에는 $i$개의 구슬이 놓인다.

각 구슬에는 수가 하나씩 적혀 있다. 이 격자 위의 부분 정삼각형이 주어질 때마다, 부분 정삼각형에 포함된 구슬에 적힌 수의 합을 출력하는 프로그램을 작성하시오.

첫째 줄에 격자의 층수 $N$이 주어진다. $(2 \le N \le 1\,500)$

다음 $N$개의 줄에는 $i$번째 줄마다 공백으로 구분된 정수 $i$개 $a_{i1}, a_{i2}, \ldots, a_{ii}$가 주어진다. $a_{ij}$는 위에서 $i$번째 층에 있는 구슬 중 왼쪽에서 $j$번째 구슬에 적힌 수이다. $(0 \le a_{ij} \le 500\,000)$

다음 줄에는 부분 정삼각형의 개수 $Q$가 주어진다. $(1 \le Q \le 500\,000)$

다음 $Q$개의 줄에는 부분 정삼각형을 정하는 세 정수 $x$, $y$, $z$가 공백으로 구분되어 주어진다. $(1 \le x \le N;\ 1 \le y \le x;\ 2 \le z \le N - x + 1)$

주어진 $x$, $y$, $z$마다 다음과 같이 정의된 부분 정삼각형에 포함된 구슬에 적힌 수의 합을 한 줄에 하나씩 출력한다.

• $0 \le i \le z - 1$을 만족하는 모든 정수 $i$에 대해, 위에서 $x+i$번째 층의 구슬 중 왼쪽에서 $y$번째부터 $y+i$번째까지의 구슬을 포함하는 정삼각형

C/C++, Java 등의 언어에서 일부 변수를 32비트 정수형으로 선언하면 오버플로우가 발생할 수 있으니 주의하라.