Masala #U0FYNDNR8C

Xotira 512 MB Vaqt 1000 ms

Kvadrat uchburchak

Sizga $n \cdot n$ $a$ jadval berilgan, va sehirgar agar siz $q$ ta so'rov ga javob bersangiz shokolad beraman deb vada berdi, afsuski sehirgar uhlashni juda hohlab turgani uchun siz unga tez javob berishingiz kerak har bir so'rov da:

$l$ va $r$ $(l \le r)$ beriladi sizni vazifangiz shunday $a_{i, j}$ lar summasini topshingiz kerak $l≤i≤j≤r$ sharti bajariladi. Rasmiy ravishda:

\sum_{i=l}^{r} \sum_{j=i}^{r} a_{i,j}

Kiruvchi ma'lumotlar:

Birinchi qatorda $n$ va $q$ ( $1 \le n \le 2500$ , $1 \le q \le 200000$ ) - satr va qatorni uzunligi va so'rovlar soni.

Keyingi $n$ qatorda jadval $a$ ( $a_{i,j} \le 10^9$ ).

Keyingi $q$ qatorda so'rovlar, har bir so'rovda $l$ va $r$ beriladi( $1 \le l \le r \le n$ )

Chiquvchi ma'lumotlar:

Har bir so'rovga javobni chiqaring - bitta butun son.

Misollar

#	input.txt	output.txt
1	3 5 15 19 11 18 20 3 9 4 4 1 2 1 1 1 2 3 3 2 2	54 15 54 4 20
2	6 7 2 1 1 1 19 5 16 13 16 7 19 8 10 2 14 14 16 13 3 7 3 16 10 4 8 12 12 1 16 17 18 12 10 6 5 4 4 4 4 5 3 6 2 3 4 4 1 2 1 5	16 42 124 43 16 16 165

input.txt

output.txt

6 7
2 1 1 1 19 5
16 13 16 7 19 8
10 2 14 14 16 13
3 7 3 16 10 4
8 12 12 1 16 17
18 12 10 6 5 4
4 4
4 5
3 6
2 3
4 4
1 2
1 5

RoboContest

Masala #U0FYNDNR8C

Kvadrat uchburchak