Du har fått tag på ett tv-spel som släppts av JOI Corp. Det är ett välgjort spel, och du har spelat det varje dag med stort nöje.

En dag dök en bana som kallas "Laser" upp bland spelarna. Det verkar som att den här banan är extremt svår, och det sägs att även skickliga spelare bara kan klara den med en mycket liten sannolikhet. När du utmanade banan många gånger insåg du att det finns en möjlighet att klara den genom att fatta mycket snabba beslut, och du tänkte att du kanske skulle kunna hantera den genom att skapa ett program.

Laserbanan utspelar sig på en plats där $N$ väggar är utplacerade. Banan är rektangulär och är uppdelad i kvadratiska rutor av storlek $1 \times 1$. Varje ruta representeras av $(x, y)$ med heltal $x, y \ge 0$. $(0, 0)$ är rutan i det nedre vänstra hörnet, och $(x, y)$ representerar rutan $x$ rutor åt höger och $y$ rutor uppåt från $(0, 0)$.

När banan börjar dyker fiender upp och attackerar. $M$ attacker utförs i följd. I den $j$-te attacken avfyrar fienden en laser rakt från rutan $(P_j, N+1)$ mot rutan $(P_j, 0)$.

Varje vägg är placerad på flera på varandra följande rutor med samma $y$-koordinat. Vägg $i$ ($1 \le i \le N$) är en rektangel med en horisontell bredd på $B_i - A_i + 1$ och en vertikal bredd på $1$. Vid banans start upptar den rutorna från $(A_i, i)$ till $(B_i, i)$. Du kan flytta väggarna horisontellt hur många gånger du vill, både före fiendens första attack och mellan vilka två fiendeattacker som helst. I ett drag kan du flytta en vägg en ruta åt höger eller en ruta åt vänster.

När en laser träffar en vägg försvagas dess kraft. Du vill minimera laserns kraft genom att flytta väggarna så att lasern träffar alla väggarna.

På den här banan vill du minimera det totala antalet väggförflyttningar.

Uppgift

Givet väggarnas startpositioner och positionerna för fiendens attacker, beräkna det minsta antalet förflyttningar för varje vägg för att säkerställa att varje laser träffar varje vägg.

Indata

Läs följande data från standard inmatning:

• Den första raden innehåller två blankstegsseparerade heltal $N$ och $M$. Detta anger att det finns $N$ väggar på denna bana och att $M$ attacker kommer att utföras.
• Den $i$-te raden av de följande $N$ raderna ($1 \le i \le N$) innehåller två blankstegsseparerade heltal $A_i$ och $B_i$. Detta anger att vägg $i$ vid banans start är placerad från rutan $(A_i, i)$ till rutan $(B_i, i)$.
• Den $j$-te raden av de följande $M$ raderna ($1 \le j \le M$) innehåller ett heltal $P_j$. Detta anger att fienden i den $j$-te attacken avfyrar en laser rakt från rutan $(P_j, N+1)$ mot rutan $(P_j, 0)$.

Utdata

Skriv ut $N$ rader till standard utmatning. Den $i$-te raden ($1 \le i \le N$) ska innehålla det minsta antalet förflyttningar för vägg $i$.

Begränsningar

All indata uppfyller följande villkor:

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

Deluppgifter

Deluppgift 1 [10 poäng]

• $N = 1$ gäller.

Deluppgift 2 [45 poäng]

• $A_i = 0$ ($1 \le i \le N$) gäller.

Deluppgift 3 [45 poäng]

• Det finns inga ytterligare begränsningar.

Exempel

Indata 1

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

Utdata 1

5
10
1
7

Förklaring

I denna indata är ett sätt att minimera antalet väggförflyttningar följande:

• Före den 1:a attacken: flytta vägg 1 åt höger 3 gånger, flytta vägg 2 åt höger 2 gånger, flytta inte vägg 3 och flytta vägg 4 åt vänster 2 gånger.
• Före den 2:a attacken: flytta inte vägg 1, flytta vägg 2 åt vänster 2 gånger, flytta inte vägg 3 och flytta vägg 4 åt vänster 2 gånger.
• Före den 3:e attacken: flytta inte vägg 1, flytta vägg 2 åt vänster 1 gång, flytta inte vägg 3 och flytta vägg 4 åt vänster 1 gång.
• Före den 4:e attacken: flytta vägg 1 åt höger 2 gånger, flytta vägg 2 åt höger 5 gånger, flytta vägg 3 åt höger 1 gång och flytta vägg 4 åt höger 2 gånger.

På detta sätt flyttas vägg 1 totalt 5 gånger, vägg 2 flyttas 10 gånger, vägg 3 flyttas 1 gång och vägg 4 flyttas 7 gånger.

Banans start

1:a attacken

2:a attacken

3:e attacken

4:e attacken

Indata 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

Utdata 2

34
178
13
6
18
0
36