Masala E

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