Se dă o matrice binară cu coloane și linii. Coloanele sunt numerotate de la stânga la dreapta cu valori de la la , iar liniile sunt numerotate de jos în sus cu valori de la la .
Matricea dată are o formă particulară, astfel că pentru fiecare coloană de la la toate elementele matricei de pe coloana respectivă au valoarea pentru toate liniile cuprinse în intervalul și în rest valoarea . Valorile sunt numere naturale date în ordine crescătoare , ).
Cerință
Să se răspundă la întrebări de forma: dându-se numerele , , , se cere suma elementelor din submatricea determinată de zona dreptunghiulară având colțul stânga-jos în coloana și linia , iar colțul dreapta-sus în coloana și linia .
Date de intrare
Fișierul de intrare este tnia.in.
- pe prima linie se găsesc două numere naturale și despărțite printr-un spațiu, cu semnificația de mai sus;
- pe a doua linie sunt cele elemente ale vectorului despărțite prin câte un spațiu;
- pe a treia linie este un număr natural ce reprezintă numărul de întrebări;
- pe următoarele linii se găsesc câte 4 numere , , , cu semnificația de mai sus, despărțite prin câte un spațiu.
Date de ieşire
Fișierul de ieșire tnia.out va conține linii reprezentând răspunsul pentru fiecare întrebare.
Restricţii și precizări
- Pentru 15 puncte: .
- Pentru alte 16 puncte: .
- Pentru alte 16 puncte: , , .
- Pentru rezolvarea corectă a cerinței se acordă 90 de puncte.
- Din oficiu se acordă 10 puncte.
Exemplu
tnia.in
5 10
2 3 7 8 10
5
1 1 5 10
2 5 4 7
3 2 3 6
3 8 3 10
3 2 3 10
tnia.out
30
6
5
0
6
Explicație
Zona dreptunghiulară având colțul stânga-jos la coloana și linia și colțul dreapta-sus la coloana și linia are suma elementelor .
Analog, pentru celelalte patru întrebări, răspunsurile corecte sunt , , și .