---
# System prepended metadata

title: Meteoriti

---

# Meteoriti

Meteorit je kamen ali kos kovine, ki na Zemljo prileti iz vesolja.  Tovrstni obiski so k sreči precej redki, tu in tam pa nas vseeno kak doleti.

Raziskovalec bi rad na podlagi podatkov o koordinatah padcev meteoritov ugotovil, koliko meteoritov je padlo na izbrana pravokotna območja.  Pomagaj mu!

Za potrebe te naloge si lahko predstavljaš, da je Zemlja ravna površina, razdeljena na enako velike kvadratne celice (vsaka od njih ima svoj par koordinat).

## Vhod

Prva vrstica vsebuje število padcev meteoritov ($n$).  Naslednjih $n$ vrstic vsebuje koordinate (najprej $x$, nato $y$) posameznih padcev.  Sledi vrstica, ki vsebuje število izbranih pravokotnih območij ($m$).  Naslednjih $m$ vrstic vsebuje podatke o območjih.  V vsaki od njih sta najprej navedeni koordinati zgornjega levega kota območja (najprej $x_1$, nato $y_1$), nato pa še koordinati spodnjega desnega kota območja (najprej $x_2$, nato $y_2$).  Širina območja potemtakem znaša $x_2 - x_1 + 1$, višina pa $y_2 - y_1 + 1$.

## Izhod

Izpiši $m$ vrstic.  V $i$-ti vrstici (za $i \in \{1, \ldots, m\}$) naj bo zapisano število meteoritov, ki je padlo na $i$-to območje.

## Primer

### Vhod

```
6
2 1
3 4
2 2
3 2
1 3
2 2
3
0 0 3 3
3 1 4 3
2 2 3 4
```

### Izhod

```
5
1
4
```

### Komentar

Na primer, na tretje območje ($x_1 = 2$, $y_1 = 2$, $x_2 = 3$, $y_2 = 4$) so padli štirje meteoriti: $(2, 2)$, $(2, 2)$, $(3, 2)$ in $(3, 4)$.

## Podnaloge

1. podnaloga (30 točk): $x_i, y_i \in [0, 1000]$ in $n, m \in [1, 1000]$.
2. podnaloga (30 točk): $x_i, y_i \in [0, 10^9]$ in $n, m \in [1, 1000]$.
3. podnaloga (40 točk): $x_i, y_i \in [0, 10^9]$ in $n, m \in [1, 30000]$.
