Zdobyłeś grę wideo wydaną przez firmę JOI. Gra jest całkiem dobrze wykonana i codziennie grasz w nią z przyjemnością.

Pewnego dnia pojawił się poziom nazywany przez graczy „Laserem”. Podobno jest on niezwykle trudny i nawet znakomici gracze przechodzą go tylko z bardzo małym prawdopodobieństwem. Po wielu próbach zauważyłeś, że być może uda się go przejść dzięki bardzo szybkiemu podejmowaniu decyzji, i pomyślałeś o napisaniu programu, który sobie z tym poradzi.

Poziom „Laser” rozgrywa się na obszarze, na którym rozmieszczono $N$ murów obronnych. Obszar jest prostokątny i podzielony na kwadratowe pola o rozmiarze $1\times 1$. Każde pole jest oznaczone parą $(x,y)$ nieujemnych liczb całkowitych. Pole $(0,0)$ znajduje się w lewym dolnym rogu, a pole $(x,y)$ leży $x$ pól na prawo i $y$ pól w górę od niego.

Po rozpoczęciu poziomu pojawia się przeciwnik, który wykonuje kolejno $M$ ataków. W ataku $j$ przeciwnik strzela laserem po linii prostej od pola $(P_j,N+1)$ w kierunku pola $(P_j,0)$.

Każdy mur zajmuje kilka kolejnych pól o tej samej współrzędnej $y$. Mur $i$ ($1 \le i \le N$) jest prostokątem o szerokości $B_i-A_i+1$ i wysokości $1$, a na początku poziomu zajmuje pola od $(A_i,i)$ do $(B_i,i)$. Bezpośrednio przed pierwszym atakiem oraz między kolejnymi atakami możesz dowolnie wiele razy przesuwać mury w lewo lub w prawo. Jeden ruch przesuwa jeden mur o jedno pole w prawo albo o jedno pole w lewo.

Gdy laser trafia w mur, jego siła maleje. Chcesz przesuwać mury tak, aby każdy laser trafił we wszystkie mury, zmniejszając jego siłę do minimum.

Chcesz wykonać na tym poziomie jak najmniej ruchów murami.

Zadanie

Dane są początkowe położenia wszystkich murów oraz pozycje kolejnych ataków przeciwnika. Wyznacz minimalną liczbę ruchów dla każdego muru przy przesuwaniu murów tak, aby każdy laser trafił we wszystkie mury.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera liczby całkowite $N$, $M$ oddzielone spacją. Oznaczają one, że na poziomie znajduje się $N$ murów i przeciwnik wykona $M$ ataków.
• Wiersz $i$ ($1 \le i \le N$) spośród następnych $N$ wierszy zawiera liczby całkowite $A_i$, $B_i$ oddzielone spacją. Oznaczają one, że na początku poziomu mur $i$ zajmuje pola od $(A_i,i)$ do $(B_i,i)$.
• Wiersz $j$ ($1 \le j \le M$) spośród następnych $M$ wierszy zawiera liczbę całkowitą $P_j$. Oznacza ona, że w ataku $j$ przeciwnik strzela laserem po linii prostej od pola $(P_j,N+1)$ w kierunku pola $(P_j,0)$.

Wyjście

Wypisz $N$ wierszy na standardowe wyjście. W wierszu $i$ ($1 \le i \le N$) wypisz minimalną liczbę ruchów muru $i$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki.

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $0 \le A_i \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $0 \le P_j \le 1\,000\,000\,000$ ($1 \le j \le M$).

Podzadania

Podzadanie 1 [10 punktów]

• Zachodzi $N=1$.

Podzadanie 2 [45 punktów]

• Zachodzi $A_i=0$ ($1 \le i \le N$).

Podzadanie 3 [45 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

Wyjście 1

5
10
1
7

Uwagi

Dla tego wejścia jeden ze sposobów przesuwania murów, który minimalizuje liczbę ruchów, jest następujący:

• Przed pierwszym atakiem przesuń mur 1 o 3 pola w prawo, mur 2 o 2 pola w prawo, nie przesuwaj muru 3 i przesuń mur 4 o 2 pola w lewo.
• Przed drugim atakiem nie przesuwaj muru 1, przesuń mur 2 o 2 pola w lewo, nie przesuwaj muru 3 i przesuń mur 4 o 2 pola w lewo.
• Przed trzecim atakiem nie przesuwaj muru 1, przesuń mur 2 o 1 pole w lewo, nie przesuwaj muru 3 i przesuń mur 4 o 1 pole w lewo.
• Przed czwartym atakiem przesuń mur 1 o 2 pola w prawo, mur 2 o 5 pól w prawo, mur 3 o 1 pole w prawo i mur 4 o 2 pola w prawo.

W ten sposób wykonasz 5 ruchów murem 1, 10 ruchów murem 2, 1 ruch murem 3 i 7 ruchów murem 4.

Stan początkowy poziomu; pierwszy atak; drugi atak; trzeci atak; czwarty atak.

Wejście 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

Wyjście 2

34
178
13
6
18
0
36