Partial Sums of a Triangle

Beads are arranged in a triangular grid as shown in the figure, so there are $\frac{N(N+1)}{2}$ beads in total. The grid has $N$ rows. Going down, each row holds more beads, so the $i$-th row from the top has $i$ beads.

Each bead has one number written on it. Each time a partial triangle on this grid is given, write a program that prints the sum of the numbers on the beads inside that partial triangle.

The first line contains the number of rows $N$. $(2 \le N \le 1\,500)$

The next $N$ lines each contain $i$ integers $a_{i1}, a_{i2}, \ldots, a_{ii}$ separated by spaces for the $i$-th line. $a_{ij}$ is the number on the bead at position $j$ from the left in the $i$-th row from the top. $(0 \le a_{ij} \le 500\,000)$

The next line contains the number of partial triangles $Q$. $(1 \le Q \le 500\,000)$

The next $Q$ lines each contain three integers $x$, $y$, and $z$ separated by spaces, which determine a partial triangle. $(1 \le x \le N;\ 1 \le y \le x;\ 2 \le z \le N - x + 1)$

For each given $x$, $y$, and $z$, print on its own line the sum of the numbers on the beads inside the partial triangle defined as follows.

• For every integer $i$ with $0 \le i \le z - 1$, the triangle includes the beads in row $x+i$ from the top, from the $y$-th bead to the $(y+i)$-th bead counted from the left.

In languages such as C/C++ and Java, declaring some variables as 32-bit integers can cause overflow.