O'rmon so'rovlari

$n \times n$ o'lchamli o'rmon xaritasi berilgan: * — daraxt, . — bo'sh joy. Qatorlar yuqoridan pastga, ustunlar chapdan o'ngga $1$ dan $n$ gacha raqamlangan. Har bir so'rovda to'g'ri to'rtburchak ichidagi daraxtlar sonini toping.

Birinchi qatorda $n$ va $q$ ($1 \le n \le 1000$, $1 \le q \le 2 \cdot 10^5$). Keyingi ta qatorda xarita. Keyingi ta qatorda , , , (, ) — to'rtburchakning yuqori chap va pastki o'ng kataklari (qator, ustun).

Har bir so'rov uchun alohida qatorda bitta son.

2D prefiks: $P_{i,j}$ — $(1, 1)$ dan $(i, j)$ gacha to'rtburchakdagi daraxtlar soni, . So'rov javobi — inklyuziya-ekskluziya: .