Du hast ein Videospiel von der Firma JOI erworben. Es ist recht gut gemacht, und du hast es jeden Tag mit einiger Freude gespielt.

Eines Tages erschien ein Level, das unter Spielern „Laser“ genannt wird. Dieses Level scheint äußerst schwierig zu sein: Selbst hervorragende Spieler schaffen es offenbar nur mit sehr geringer Wahrscheinlichkeit. Nach vielen Versuchen hast du bemerkt, dass du es durch sehr schnelle Entscheidungen möglicherweise schaffen könntest, und überlegt, ob du dafür ein Programm schreiben könntest.

Das Laser-Level spielt auf einem Feld mit $N$ Schutzwänden. Das Feld ist rechteckig und in quadratische Zellen der Größe $1\times1$ unterteilt. Jede Zelle wird durch nichtnegative ganze Zahlen $x,y$ als $(x,y)$ bezeichnet. $(0,0)$ ist die Zelle in der linken unteren Ecke, und $(x,y)$ bezeichnet die Zelle, die von $(0,0)$ aus $x$ Zellen rechts und $y$ Zellen oberhalb liegt.

Zu Beginn des Levels erscheint ein Gegner und greift an. Es erfolgen nacheinander $M$ Angriffe. Beim $j$-ten Angriff schießt der Gegner einen Laser geradlinig von der Zelle $(P_j,N+1)$ in Richtung der Zelle $(P_j,0)$.

Jede Schutzwand belegt mehrere aufeinanderfolgende Zellen mit derselben $y$-Koordinate. Schutzwand $i$ ($1 \le i \le N$) ist ein Rechteck mit einer horizontalen Breite von $B_i-A_i+1$ und einer vertikalen Höhe von $1$. Zu Beginn des Levels belegt sie die Zellen von $(A_i,i)$ bis $(B_i,i)$. Unmittelbar vor dem ersten Angriff sowie zwischen den Angriffen kannst du die Schutzwände beliebig oft nach links oder rechts verschieben. Bei einer Bewegung kannst du eine Schutzwand um eine Zelle nach rechts oder um eine Zelle nach links verschieben.

Wenn ein Laser auf eine Schutzwand trifft, wird er schwächer. Du möchtest die Stärke des Lasers minimieren, indem du die Schutzwände so verschiebst, dass der Laser auf alle Schutzwände trifft.

Du möchtest die Anzahl der Bewegungen der Schutzwände in diesem Level so klein wie möglich halten.

Aufgabe

Gegeben sind die Anfangspositionen aller Schutzwände und die Positionen der einzelnen Angriffe des Gegners. Bestimme für jede Schutzwand die minimale Anzahl von Bewegungen, wenn die Schutzwände so verschoben werden, dass jeder Laser auf jede Schutzwand trifft.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält die durch Leerzeichen getrennten ganzen Zahlen $N,M$. Das bedeutet, dass es in diesem Level $N$ Schutzwände gibt und der Gegner $M$ Angriffe durchführt.
• Die $i$-te Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen enthält die durch Leerzeichen getrennten ganzen Zahlen $A_i,B_i$. Das bedeutet, dass Schutzwand $i$ zu Beginn des Levels die Zellen von $(A_i,i)$ bis $(B_i,i)$ belegt.
• Die $j$-te Zeile ($1 \le j \le M$) der folgenden $M$ Zeilen enthält eine ganze Zahl $P_j$. Das bedeutet, dass der Gegner beim $j$-ten Angriff einen Laser geradlinig von der Zelle $(P_j,N+1)$ in Richtung der Zelle $(P_j,0)$ schießt.

Ausgabe

Gib $N$ Zeilen auf der Standardausgabe aus. Die $i$-te Zeile ($1 \le i \le N$) soll die minimale Anzahl von Bewegungen der Schutzwand $i$ enthalten.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

• Es gilt $N=1$.

Teilaufgabe 2 [45 Punkte]

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

Teilaufgabe 3 [45 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

5
10
1
7

Hinweis

Für diese Eingabe ist eine Möglichkeit, die Anzahl der Bewegungen der Schutzwände zu minimieren, die folgende:

• Vor dem ersten Angriff verschiebst du Schutzwand $1$ dreimal nach rechts, Schutzwand $2$ zweimal nach rechts, Schutzwand $3$ gar nicht und Schutzwand $4$ zweimal nach links.
• Vor dem zweiten Angriff verschiebst du Schutzwand $1$ gar nicht, Schutzwand $2$ zweimal nach links, Schutzwand $3$ gar nicht und Schutzwand $4$ zweimal nach links.
• Vor dem dritten Angriff verschiebst du Schutzwand $1$ gar nicht, Schutzwand $2$ einmal nach links, Schutzwand $3$ gar nicht und Schutzwand $4$ einmal nach links.
• Vor dem vierten Angriff verschiebst du Schutzwand $1$ zweimal nach rechts, Schutzwand $2$ fünfmal nach rechts, Schutzwand $3$ einmal nach rechts und Schutzwand $4$ zweimal nach rechts.

Dabei wird Schutzwand $1$ insgesamt $5$-mal, Schutzwand $2$ insgesamt $10$-mal, Schutzwand $3$ insgesamt $1$-mal und Schutzwand $4$ insgesamt $7$-mal verschoben.

Zu Beginn des Levels; erster Angriff; zweiter Angriff; dritter Angriff; vierter Angriff.

Eingabe 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

Ausgabe 2

34
178
13
6
18
0
36