Has conseguido un videojuego publicado por la compañía JOI. Es un juego bastante bien hecho y llevabas un tiempo disfrutándolo cada día.

Un día apareció un nivel al que los jugadores llaman «Láser». Parece ser extremadamente difícil: incluso los jugadores más hábiles solo logran superarlo con una probabilidad muy pequeña. Tras intentarlo muchas veces, te diste cuenta de que podrías superarlo tomando decisiones muy rápidas y pensaste que tal vez podrías hacerlo mediante un programa.

El nivel Láser se desarrolla en un escenario con $N$ muros defensivos. El escenario es rectangular y está dividido en casillas cuadradas de $1 \times 1$. Cada casilla se representa mediante $(x,y)$, donde $x,y$ son enteros no negativos. La casilla $(0,0)$ está en la esquina inferior izquierda, y $(x,y)$ es la casilla situada $x$ posiciones a la derecha e $y$ posiciones hacia arriba desde $(0,0)$.

Al comenzar el nivel aparece un enemigo que realiza $M$ ataques, en orden. En el ataque $j$, dispara un láser en línea recta desde la casilla $(P_j,N+1)$ hacia la casilla $(P_j,0)$.

Cada muro ocupa varias casillas consecutivas con la misma coordenada $y$. El muro $i$ ($1 \le i \le N$) es un rectángulo de anchura horizontal $B_i-A_i+1$ y altura $1$; al comenzar el nivel ocupa desde la casilla $(A_i,i)$ hasta la casilla $(B_i,i)$. Justo antes del primer ataque y entre dos ataques puedes mover los muros horizontalmente tantas veces como quieras. Cada movimiento desplaza un muro una casilla a la derecha o una casilla a la izquierda.

El láser pierde potencia al chocar con un muro. Quieres minimizar su potencia moviendo los muros para que el láser choque con todos ellos.

Quieres realizar el menor número posible de movimientos de los muros en este nivel.

Tarea

Se dan las posiciones iniciales de los muros y las posiciones de los ataques del enemigo. Calcula, para cada muro, el número mínimo de movimientos necesarios para que todos los láseres choquen con todos los muros.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene dos enteros $N,M$, separados por un espacio. Indican que hay $N$ muros y que el enemigo realiza $M$ ataques.
• La línea $i$ ($1 \le i \le N$) de las siguientes $N$ líneas contiene dos enteros $A_i,B_i$, separados por un espacio. Indican que, al comenzar el nivel, el muro $i$ ocupa desde la casilla $(A_i,i)$ hasta la casilla $(B_i,i)$.
• La línea $j$ ($1 \le j \le M$) de las siguientes $M$ líneas contiene un entero $P_j$. Indica que, en el ataque $j$, el enemigo dispara un láser en línea recta desde $(P_j,N+1)$ hacia $(P_j,0)$.

Salida

Escribe $N$ líneas en la salida estándar. La línea $i$ ($1 \le i \le N$) debe contener el número mínimo de movimientos del muro $i$.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

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

Subtareas

Subtarea 1 [10 puntos]

• $N=1$.

Subtarea 2 [45 puntos]

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

Subtarea 3 [45 puntos]

Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

5
10
1
7

Nota

Una forma de mover los muros que minimiza sus movimientos es la siguiente:

• Antes del primer ataque, mueve el muro $1$ tres veces a la derecha y el muro $2$ dos veces a la derecha, deja el muro $3$ inmóvil y mueve el muro $4$ dos veces a la izquierda.
• Antes del segundo ataque, deja el muro $1$ inmóvil, mueve el muro $2$ dos veces a la izquierda, deja el muro $3$ inmóvil y mueve el muro $4$ dos veces a la izquierda.
• Antes del tercer ataque, deja el muro $1$ inmóvil, mueve el muro $2$ una vez a la izquierda, deja el muro $3$ inmóvil y mueve el muro $4$ una vez a la izquierda.
• Antes del cuarto ataque, mueve el muro $1$ dos veces a la derecha, el muro $2$ cinco veces a la derecha, el muro $3$ una vez a la derecha y el muro $4$ dos veces a la derecha.

Con estos movimientos, el muro $1$ se mueve 5 veces, el muro $2$ se mueve 10 veces, el muro $3$ se mueve 1 vez y el muro $4$ se mueve 7 veces.

Al comenzar el nivel; primer ataque; segundo ataque; tercer ataque; cuarto ataque.

Entrada 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

Salida 2

34
178
13
6
18
0
36