Ўрмон сўровлари

$n \times n$ ўлчамли ўрмон харитаси берилган: * — дарахт, . — бўш жой. Қаторлар юқоридан пастга, устунлар чапдан ўнгга $1$ дан $n$ гача рақамланган. Ҳар бир сўровда тўғри тўртбурчак ичидаги дарахтлар сонини топинг.

Биринчи қаторда $n$ ва $q$ ($1 \le n \le 1000$, $1 \le q \le 2 \cdot 10^5$). Кейинги та қаторда харита. Кейинги та қаторда , , , (, ) — тўртбурчакнинг юқори чап ва пастки ўнг катаклари (қатор, устун).

Ҳар бир сўров учун алоҳида қаторда битта сон.

2D префикс: $P_{i,j}$ — $(1, 1)$ дан $(i, j)$ гача тўртбурчакдаги дарахтлар сони, . Сўров жавоби — инклюзия-эксклюзия: .