Hai ottenuto un videogioco pubblicato da JOI Corp. È un gioco ben fatto e ci stai giocando ogni giorno con un certo divertimento.

Un giorno, tra i giocatori è apparso un livello chiamato "Laser". Sembra che questo livello sia estremamente difficile e si dice che persino i giocatori eccellenti riescano a superarlo solo con una probabilità molto bassa. Affrontando il livello molte volte, ti sei reso conto che c'è la possibilità di superarlo prendendo decisioni molto rapide e hai pensato di poterci riuscire creando un programma.

Il livello del laser è ambientato in un luogo in cui sono posizionati $N$ muri. Il livello è rettangolare ed è diviso in celle quadrate $1 \times 1$. Ogni cella è rappresentata da $(x, y)$ usando interi $x, y \ge 0$. $(0, 0)$ è la cella nell'angolo in basso a sinistra, e $(x, y)$ rappresenta la cella che si trova $x$ celle a destra e $y$ celle in alto rispetto a $(0, 0)$.

Quando il livello inizia, compaiono i nemici e attaccano. Vengono eseguiti $M$ attacchi in sequenza. Nel $j$-esimo attacco, il nemico spara un raggio laser in linea retta dalla cella $(P_j, N+1)$ verso la cella $(P_j, 0)$.

Ogni muro è posizionato su diverse celle consecutive aventi la stessa coordinata $y$. Il muro $i$ ($1 \le i \le N$) è un rettangolo con larghezza orizzontale $B_i - A_i + 1$ e altezza verticale $1$. All'inizio del livello, esso occupa le celle da $(A_i, i)$ a $(B_i, i)$. Puoi spostare i muri orizzontalmente quante volte vuoi, sia prima del primo attacco nemico sia tra due attacchi nemici consecutivi. In una mossa, puoi spostare un muro di una cella a destra oppure di una cella a sinistra.

Quando un laser colpisce un muro, la sua potenza si indebolisce. Vuoi ridurre al minimo la potenza del laser spostando i muri in modo che il laser colpisca tutti i muri.

In questo livello, vuoi minimizzare il numero totale di spostamenti dei muri.

Compito

Date le posizioni iniziali dei muri e le posizioni degli attacchi nemici, calcola il numero minimo di spostamenti per ciascun muro affinché ogni laser colpisca ogni muro.

Formato di input

Leggi i seguenti dati dallo standard input:

• La prima riga contiene due interi separati da spazio $N$ e $M$. Questo indica che ci sono $N$ muri in questo livello e che verranno eseguiti $M$ attacchi.
• La $i$-esima riga delle successive $N$ righe ($1 \le i \le N$) contiene due interi separati da spazio $A_i$ e $B_i$. Questo indica che all'inizio del livello il muro $i$ è posizionato dalla cella $(A_i, i)$ alla cella $(B_i, i)$.
• La $j$-esima riga delle successive $M$ righe ($1 \le j \le M$) contiene un intero $P_j$. Questo indica che nel $j$-esimo attacco il nemico spara un laser in linea retta dalla cella $(P_j, N+1)$ verso la cella $(P_j, 0)$.

Formato di output

Stampa $N$ righe sullo standard output. La $i$-esima riga ($1 \le i \le N$) deve contenere il numero minimo di spostamenti per il muro $i$.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni:

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

Subtask

Subtask 1 [10 punti]

• Vale $N = 1$.

Subtask 2 [45 punti]

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

Subtask 3 [45 punti]

• Non ci sono vincoli aggiuntivi.

Esempi

Input 1

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

Output 1

5
10
1
7

Note

In questo input, un modo per minimizzare il numero di spostamenti dei muri è il seguente:

• Prima del 1° attacco, sposta il muro 1 a destra 3 volte, sposta il muro 2 a destra 2 volte, non spostare il muro 3 e sposta il muro 4 a sinistra 2 volte.
• Prima del 2° attacco, non spostare il muro 1, sposta il muro 2 a sinistra 2 volte, non spostare il muro 3 e sposta il muro 4 a sinistra 2 volte.
• Prima del 3° attacco, non spostare il muro 1, sposta il muro 2 a sinistra 1 volta, non spostare il muro 3 e sposta il muro 4 a sinistra 1 volta.
• Prima del 4° attacco, sposta il muro 1 a destra 2 volte, sposta il muro 2 a destra 5 volte, sposta il muro 3 a destra 1 volta e sposta il muro 4 a destra 2 volte.

In questo modo, il muro 1 viene spostato 5 volte, il muro 2 viene spostato 10 volte, il muro 3 viene spostato 1 volta e il muro 4 viene spostato 7 volte.

Inizio del livello

1° attacco

2° attacco

3° attacco

4° attacco

Input 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

Output 2

34
178
13
6
18
0
36