---
# System prepended metadata

title: Fontana

---

<table border=0>
<tr>
<td width="80%">
EJOI 2020 Day 1 </br>
<b>fountain</b> (Slovene)
</td>
<td width="20%">
<img align="right" width="100"  src="https://i.imgur.com/KUVHoM0.png">
</td>
</tr>
</table>




# Fontana

## Naloga

Fontana je sestavljena iz $N$ navpično poravnanih krožnih hranilnikov, ki so oštevilčeni od zgoraj navzdol začenši z $1$.

![](https://i.imgur.com/RsZQVMb.png)

Za vsak hranilnik s pipo sta podana premer in prostornina, zraven pa mu pripada še pipa, iz katere lahko izteče poljubna količina vode v hranilnik. Ko se hranilnik napolni, preostanek vode steče v prvi po premeru **strogo večji** hranilnik pod njim ali v odtok, če takšnega hranilnika ni. 

Tvoja naloga je, da odgovoriš na $Q$ neodvisnih poizvedb, ki se glase: V katerem hranilniku se tok vode ustavi, če iz pipe $R_i$-tega hranilnika izpustimo $V_i$ litrov vode? Če se tok vode nadaljuje v odtok (se ne ustavi v nobenem hranilniku), izpiši $0$. 

## Vhod

V prvi vrstici vhoda se nahajata celi števili $N$ in $Q$.
V naslednjih $N$ vrsticah se nahaja par celih števil $D_i$ in $C_i$, kjer je $D_i$ premer in $C_i$ prostornina (v litrih) $i$-tega hranilnika.
V naslednjih $Q$ vrsticah se nahajata celi števili $R_i$ in $V_i$.

## Izhod

Izpiši $Q$ vrstic s celim številom. V vsako vrstico izpiši odgovor na vprašanje kot so si sledila na vhodu.

## Omejitve

* $2 \leq N \leq 10^5$
* $1 \leq Q \leq 2 \cdot 10^5$
* $1 \leq C_i \leq 1000$
* $1 \leq D_i, V_i \leq 10^9$
* $1 \leq R_i \leq N$


## Podnaloge

1. podnaloga (30 točk): $N \leq 1000$ in $Q \leq 2000$
2. podnaloga (30 točk): Premeri hranilnikov strogo naraščajo od zgoraj navzdol $(D_i < D_{i+1})$
3. podnaloga (40 točk): Ni dodatnih omejitev.

## Primer

### Vhod

```
6 5
4 10
6 8
3 5
4 14
10 9
4 20 
1 25
6 30
5 8
3 13
2 8
```

### Izhod

```
5
0
5
4
2
```

Prvi dve poizvedbi sta prikazani na zgornji sliki.
Ker so poizvedbe med seboj neodvisne, v tretjem primeru voda ne bo iztekla iz $5.$ hranilnika.

