Vous avez obtenu un jeu vidéo édité par la société JOI. Le jeu est plutôt bien conçu et vous y jouiez chaque jour avec un certain plaisir.

Un jour, un niveau que les joueurs appellent « Laser » est apparu. Ce niveau semble extrêmement difficile : même les meilleurs joueurs n'auraient qu'une très faible chance de le terminer. Après de nombreuses tentatives, vous avez remarqué qu'il était peut-être possible de réussir en prenant des décisions très rapidement, et vous avez pensé qu'un programme pourrait vous aider.

Le niveau Laser se déroule dans un espace où sont disposés $N$ murs de protection. Cet espace est rectangulaire et divisé en cases carrées de taille $1 \times 1$. Chaque case est désignée par $(x,y)$, où $x,y$ sont des entiers positifs ou nuls. La case $(0,0)$ est celle du coin inférieur gauche, et $(x,y)$ désigne la case située $x$ cases à droite et $y$ cases au-dessus de $(0,0)$.

Au début du niveau, un ennemi apparaît et attaque. Il effectue successivement $M$ attaques. Lors de la $j$-ème attaque, il tire un laser en ligne droite depuis la case $(P_j,N+1)$ vers la case $(P_j,0)$.

Chaque mur occupe plusieurs cases consécutives de même ordonnée. Le mur $i$ ($1 \le i \le N$) est un rectangle de largeur $B_i-A_i+1$ et de hauteur $1$. Au début du niveau, il occupe les cases de $(A_i,i)$ à $(B_i,i)$. Vous pouvez déplacer les murs horizontalement autant de fois que vous le souhaitez juste avant la première attaque et entre deux attaques. Un déplacement consiste à déplacer un mur d'une case vers la droite ou d'une case vers la gauche.

Lorsqu'un laser heurte un mur, sa puissance diminue. Vous voulez réduire sa puissance au minimum en déplaçant les murs afin que chaque laser heurte tous les murs.

Vous souhaitez effectuer le moins de déplacements possible dans ce niveau.

Tâche

On vous donne la position initiale de chaque mur et la position de chaque attaque ennemie. Pour chaque mur, déterminez le nombre minimal de déplacements nécessaires afin que tous les lasers heurtent tous les murs.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient les entiers $N,M$ séparés par un espace. Ils indiquent que le niveau contient $N$ murs et que l'ennemi effectue $M$ attaques.
• La $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes contient les entiers $A_i,B_i$ séparés par un espace. Ils indiquent qu'au début du niveau, le mur $i$ occupe les cases de $(A_i,i)$ à $(B_i,i)$.
• La $j$-ème ligne ($1 \le j \le M$) des $M$ lignes suivantes contient un entier $P_j$. Il indique que, lors de la $j$-ème attaque, l'ennemi tire un laser en ligne droite depuis la case $(P_j,N+1)$ vers la case $(P_j,0)$.

Sortie

Écrivez $N$ lignes sur la sortie standard. La $i$-ème ligne ($1 \le i \le N$) doit contenir le nombre minimal de déplacements du mur $i$.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

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

Sous-tâches

Sous-tâche 1 [10 points]

• $N=1$.

Sous-tâche 2 [45 points]

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

Sous-tâche 3 [45 points]

Il n'y a pas de contraintes supplémentaires.

Exemples

Entrée 1

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

Sortie 1

5
10
1
7

Remarque

Pour cette entrée, voici une manière de déplacer les murs qui minimise le nombre de déplacements :

• Avant la première attaque, déplacez le mur $1$ trois fois vers la droite, le mur $2$ deux fois vers la droite, ne déplacez pas le mur $3$ et déplacez le mur $4$ deux fois vers la gauche.
• Avant la deuxième attaque, ne déplacez pas le mur $1$, déplacez le mur $2$ deux fois vers la gauche, ne déplacez pas le mur $3$ et déplacez le mur $4$ deux fois vers la gauche.
• Avant la troisième attaque, ne déplacez pas le mur $1$, déplacez le mur $2$ une fois vers la gauche, ne déplacez pas le mur $3$ et déplacez le mur $4$ une fois vers la gauche.
• Avant la quatrième attaque, déplacez le mur $1$ deux fois vers la droite, le mur $2$ cinq fois vers la droite, le mur $3$ une fois vers la droite et le mur $4$ deux fois vers la droite.

Ainsi, le mur $1$ est déplacé 5 fois, le mur $2$ 10 fois, le mur $3$ une fois et le mur $4$ 7 fois.

Début du niveau ; première attaque ; deuxième attaque ; troisième attaque ; quatrième attaque.

Entrée 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

Sortie 2

34
178
13
6
18
0
36