#166Qiyin

To'rtburchaklarni sanash

Vaqt: 1 s · Xotira: 256 MB

Prefiks yig'indilar

Shart

Sizda $n$ ta to'g'ri to'rtburchak bor, $i$ -sining balandligi $h_i$ , eni $w_i$ . $q$ ta so'rov beriladi: har birida $h_s, w_s, h_b, w_b$ sonlari. $h_s < h_i < h_b$ va $w_s < w_i < w_b$ shartlarini (qat'iy tengsizliklar) qanoatlantiradigan barcha to'rtburchaklar yuzlari yig'indisini $\sum h_i w_i$ toping. To'rtburchaklarni aylantirib bo'lmaydi.

Kirish formati

Birinchi qatorda $n$ va $q$ ( $1 \le n, q \le 10^5$ ). Keyingi ta qatorda va (). Keyingi ta qatorda , , , (, ).

Chiqish formati

Har bir so'rov uchun alohida qatorda bitta son.

Namunalar

Kirish

Chiqish

Kirish

5 5
1 1
2 2
3 3
4 4
5 5
3 3 6 6
2 1 4 5
1 1 2 10
1 1 100 100
1 1 3 3

Chiqish

Izoh

O'lchamlar kichik: $1000 \times 1000$ jadval tuzing, $c_{h,w}$ — balandligi $h$ , eni $w$ bo'lgan to'rtburchaklar yuzlari yig'indisi. Uning 2D prefiksi bilan har bir so'rov — qatorlar va ustunlar to'rtburchagi yig'indisi, .