Problem 926: triunghi

Se consideră $A$ un tablou bidimensional cu $n$ linii, $n$ coloane și elemente numere naturale. O zonă triunghiulară a tabloului, reprezentată de tripletul ( $lin, col, k$ ), este o zonă de forma unui triunghi dreptunghic cu catetele de lungime egală cu $|k|$ , definită astfel:

Pentru $k > 0$ , zona este compusă din $k$ linii:

pe prima linie a zonei se află elementele $A[lin][col], A[lin][col+1], \dots, A[lin][col+k-1]$ ;
pe a doua linie a zonei se află elementele $A[lin+1][col], A[lin+1][col+1], \dots, A[lin+1][col+k-2]$ ;
pe a treia linie a zonei se află elementele $A[lin+2][col], A[lin+2][col+1], \dots, A[lin+2][col+k-3]$ ;
$\dots$ ;
pe ultima linie a zonei se află elementul $A[lin+k-1][col]$ .

Pentru $k<0$ , zona este compusă din $|k|=-k$ linii:

pe prima linie a zonei se află elementul $A[lin-|k|+1][col]$ ;
pe a doua linie a zonei se află elementele $A[lin-|k|+2][col-1], A[lin-|k|+2][col]$ ;
$\dots$ ;
pe ultima linie a zonei se află elementele $A[lin][col-|k|+1], A[lin][col-|k|+2], \dots, A[lin][col]$ .

Suma elementelor ce compun o zonă triunghiulară se numește suma zonei.

Cerință

Scrieţi un program care, cunoscând tabloul $A$ şi $Q$ zone triunghiulare, determină cea mai mare dintre sumele zonelor.

Date de intrare

Fișierul de intrare triunghi.in conține pe prima linie numărul natural $n$ , cu semnificaţia din enunţ. Pe următoarele $n$ linii se găsesc câte $n$ valori naturale, reprezentând elementele tabloului $A$ . Pe linia $n + 2$ se află numărul natural $Q$ , reprezentând numărul zonelor triunghiulare. Pe următoarele $Q$ linii se găsesc tripletele de valori $lin \ col \ k$ , care reprezintă cele $Q$ zone, în forma descrisă în enunţ. Valorile aflate pe aceeaşi linie a fişierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire triunghi.out va conține o singură linie pe care va fi scris un număr natural reprezentând suma maximă cerută.

Restricții și precizări

$3 \leq n \leq 1 \ 000$ ; $1 \leq Q \leq 100 \ 000$ ; $2 \leq |k| \leq n$ ;
Valorile din tablou sunt numere naturale din intervalul [ $1, 100$ ].
Liniile şi coloanele tabloului $A$ sunt numerotate de la $1$ la $n$ (liniile de sus în jos, iar coloanele de la stânga la dreapta).
$|k|$ reprezintă modulul numărului $k$ ( $k$ , pentru $k \geq 0$ , respectiv $-k$ , pentru $k < 0$ ).
Se garantează că orice zonă triunghiulară dintre cele $Q$ este complet inclusă în tabloul $A$ .

Exemplu

triunghi.in

6
5 8 10 4 9 4
2 10 10 2 4 8
8 10 3 4 6 6
4 6 9 7 1 9
6 7 2 2 10 6
10 4 6 1 10 4
3
4 1 3
4 4 -4
6 5 -2

triunghi.out

Explicație

Zona triunghiulară de sumă maximă ( $59$ ) este reprezentată de tripletul ( $4 ,\ 4 ,\ -4$ ) și conține valorile evienţiate: $59 = 4 + (10 + 2) + (10 + 3 + 4) + (4 + 6 + 9 + 7)$ .

triunghi