Problem description

Jedną z największych atrakcji turystycznych w Górach Badziewnych jest Rząd Drzew na Nudnawej Polanie, u podnóża Niepozornego Szczytu. Jak się można domyślić, jest to po prostu N drzew zasadzonych obok siebie w rzędzie.

Rząd Drzew jest dumą całego regionu, lecz z roku na rok staje się on coraz mniej okazały. Wszystko to za sprawą silnych wiatrów. Co roku, mniej więcej w okolicach października, zrywa się silny halny. Wieje on z Niepozornego Szczytu w kierunku Rzędu Drzew, zawsze od zachodu i powala niektóre drzewa. To, które dokładnie, zależy od wytrzymałości i wysokości drzew. Nieprzewrócone drzewo o wysokości h osłania drzewa posadzone na wschód od niego, które mają wysokość h lub mniejszą. Drzewa są zasadzone na tyle daleko od siebie, że powalone drzewo nie przewraca żadnych innych drzew, może ono jednak odsłonić inne drzewa, narażając je na działanie wiatru.

Instytut Meteorologii w Przekopanem przyjrzał się bliżej zjawisku corocznego halnego na Nudnawej Polanie. Profesor Andrzej Bachleda–Korpiel–Śliwka–Gąsienica–Bułecka opracował skomplikowany model, dzięki któremu może dokładnie przewidzieć siłę corocznych wiatrów. Siła wiatru jest charakteryzowana przez jedną liczbę – największą wytrzymałość powalanego przez ten wiatr drzewa.

Mając informacje o wytrzymałości i wysokości wszystkich drzew, a także prognozy siły wiatru w kolejnych latach, oblicz ile drzew zostanie powalonych po każdym roku.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone odstępem – oznaczają one kolejno liczbę drzew na polanie oraz liczbę corocznych prognoz.

W kolejnych N wierszach znajduje się opis poszczególnych drzew na polanie, od zachodu na wschód. Opis drzewa składa się z dwóch liczb naturalnych H_i oraz W_i, oddzielonych odstępem. Oznaczają one wysokość oraz wytrzymałość drzewa.

W kolejnych M wierszach znajdują się prognozy dla kolejnych lat. Prognoza składa się z jednej liczby naturalnej S_i, oznaczającej siłę wiatru. Dokładniej oznacza to, że wiatr powali wszystkie nieosłonięte drzewa o wytrzymałości S_i lub mniejszej.

Wyjście

Twój program powinien wypisać na wyjście M wierszy. W i-tym wierszu powinna się znaleźć liczba drzew powalonych przez halny w i-tym roku.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ M ≤ 300 000, 1 ≤ H_i, W_i, S_i ≤ 10⁹.

Przykład

5 5
4 30
4 20
3 10
6 10
3 20
9
10
20
30
30

0
1
0
4
0