Na matfyze sa v budúcom semestri bude prednášať $n$ prednášok. Každá už má presne stanovený čas začiatku a konca (zadané ako celé čísla $z_i$ a $k_i$). Taktiež pre jednoduchosť predpokladajme, že každá prednáška môže byť robená v ľubovoľnej miestnosti.
Samozrejme, dve prednášky nesmú byť v tej istej miestnosti, ak sa ich intervaly časov prekrývajú. (Každá prednáška je uzavretý interval. Za prekryv sa teda počíta aj to, ak v nejakom okamihu jedna z prednášok začína a druhá končí.)
Pre každú z $q$ otázok nájdite najmenší možný počet prednáškových miestností, ktorý stačí na to, aby mohli (po vhodnom rozmiestnení do nich) prebehnúť úplne všetky dané prednášky v čase $q_i$.
Pre jednoduchosť nám bude stačiť, keď zistíte optimálny počet miestností. Netreba už zostrojiť a vypísať konkrétne rozmiestnenie prednášok do miestností.
V prvom riadku je číslo $n$: počet prednášok a $q$: počet otázok.
Nasleduje $n$ riadkov a v každom z nich dve celé čísla popisujúce jednu prednášku: čas jej začiatku $z_i$ a čas jej konca $k_i$.
Na poslednom riadku je $q$ čísiel $q_i$: časy, v ktorých chceme vedieť odpoveď.
Počet prednášok a otázok v žiadnom testovacom prípade neprekročí $200 000$. Časy sú z rozsahu od $0$ do $2 \cdot 10^9$.
Vypíšte jeden riadok a v ňom odpovede na príslušné otázky.
2 5
10 20
20 30
0 10 20 30 40
0 1 2 1 0
2 5
21 30
10 20
0 10 20 21 30
0
1
1
1
1
4 4
30 70
20 80
72 95
65 73
50 30 72 60
2 2 3 2