AL06-4. To‘g‘ri to‘rtburchak yig‘indisi

n × m jadval va q ta so‘rov berilgan. Har so‘rov — to‘g‘ri to‘rtburchak: r1 c1 r2 c2 (chap-yuqori va o‘ng-pastki kataklar). Ichidagi sonlar yig‘indisini toping.

Ikki o‘lchamli prefiks P[i][j] — (1; 1) dan (i; j) gacha bo‘lgan yig‘indi. Javob to‘rtta qiymatdan yig‘iladi — rasmdagi formulaga qarang.

Kirish ma’lumotlari

Birinchi qatorda n m. Keyingi n qatorda m tadan son. So‘ng q va q qatorda r1 c1 r2 c2.

Chiqish ma’lumotlari

q qator — yig‘indilar.

Cheklovlar

1 ≤ n, m ≤ 500, 1 ≤ q ≤ 10⁵, |sonlar| ≤ 1000