삼각형의 부분합

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

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

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

다음 $N$개의 줄에 걸쳐, $i$번째 줄에는 $i$개의 정수 $a\_{i1}, a\_{i2}, ..., 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)$

$Q$개의 줄에 걸쳐 한 줄에 하나씩, 주어진 $x$, $y$, $z$에 대하여, 다음과 같이 정의되는 부분 정삼각형에 포함되는 구슬에 적힌 수의 합을 출력한다.

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

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