Você conseguiu um videojogo lançado pela empresa JOI. O jogo é bastante bem feito, e você jogava todos os dias, divertindo-se razoavelmente.

Um dia, surgiu uma fase que os jogadores chamam de “Laser”. Ao que parece, essa fase é extremamente difícil, e até os melhores jogadores só conseguem completá-la com uma probabilidade muito pequena. Ao tentar a fase repetidamente, você percebeu que talvez fosse possível completá-la tomando decisões muito rápidas, e pensou em escrever um programa para lidar com ela.

A fase Laser decorre num cenário onde estão colocadas $N$ barreiras. O cenário é retangular e está dividido em células quadradas de $1\times1$. Cada célula é representada por $(x,y)$, em que $x,y$ são inteiros não negativos. A célula $(0,0)$ fica no canto inferior esquerdo, e $(x,y)$ é a célula que fica $x$ células à direita e $y$ células acima de $(0,0)$.

Quando a fase começa, aparece um inimigo que realiza ataques. São realizados $M$ ataques por ordem. No $j$-ésimo ataque, o inimigo dispara um laser em linha reta da célula $(P_j,N+1)$ em direção à célula $(P_j,0)$.

Cada barreira ocupa várias células consecutivas com a mesma coordenada $y$. A barreira $i$ ($1\le i\le N$) é um retângulo com largura horizontal $B_i-A_i+1$ e altura $1$; no início da fase, ocupa as células de $(A_i,i)$ a $(B_i,i)$. Você pode mover as barreiras para a esquerda ou para a direita quantas vezes quiser, imediatamente antes do primeiro ataque do inimigo e entre os ataques. Num movimento, pode deslocar uma barreira uma célula para a direita ou uma célula para a esquerda.

O laser perde força ao atingir uma barreira. Você quer minimizar a força dos lasers, movendo as barreiras de modo que cada laser atinja todas as barreiras.

Nesta fase, você quer minimizar o número de movimentos das barreiras.

Tarefa

São dadas as posições de todas as barreiras no início da fase e a posição de cada ataque do inimigo. Determine, para cada barreira, o número mínimo de movimentos necessários para que todos os lasers atinjam todas as barreiras.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $N,M$ separados por um espaço. Isto significa que há $N$ barreiras nesta fase e que o inimigo realiza $M$ ataques.
• A $i$-ésima linha ($1\le i\le N$) das $N$ linhas seguintes contém os inteiros $A_i,B_i$ separados por um espaço. Isto significa que, no início da fase, a barreira $i$ ocupa as células de $(A_i,i)$ a $(B_i,i)$.
• A $j$-ésima linha ($1\le j\le M$) das $M$ linhas seguintes contém um inteiro $P_j$. Isto significa que, no $j$-ésimo ataque, o inimigo dispara um laser em linha reta da célula $(P_j,N+1)$ em direção à célula $(P_j,0)$.

Saída

Escreva $N$ linhas na saída padrão. Na $i$-ésima linha ($1\le i\le N$), escreva o número mínimo de movimentos da barreira $i$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $1\le N\le200\,000$.
• $1\le M\le200\,000$.
• $0\le A_i\le B_i\le1\,000\,000\,000$ ($1\le i\le N$).
• $0\le P_j\le1\,000\,000\,000$ ($1\le j\le M$).

Subtarefas

Subtarefa 1 [10 pontos]

• Satisfaz $N=1$.

Subtarefa 2 [45 pontos]

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

Subtarefa 3 [45 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

5
10
1
7

Nota

Para esta entrada, uma maneira de mover as barreiras que minimiza o número de movimentos é a seguinte:

• Antes do primeiro ataque, mova a barreira $1$ três vezes para a direita, a barreira $2$ duas vezes para a direita, não mova a barreira $3$ e mova a barreira $4$ duas vezes para a esquerda.
• Antes do segundo ataque, não mova a barreira $1$, mova a barreira $2$ duas vezes para a esquerda, não mova a barreira $3$ e mova a barreira $4$ duas vezes para a esquerda.
• Antes do terceiro ataque, não mova a barreira $1$, mova a barreira $2$ uma vez para a esquerda, não mova a barreira $3$ e mova a barreira $4$ uma vez para a esquerda.
• Antes do quarto ataque, mova a barreira $1$ duas vezes para a direita, a barreira $2$ cinco vezes para a direita, a barreira $3$ uma vez para a direita e a barreira $4$ duas vezes para a direita.

Com estes movimentos, a barreira $1$ é movida 5 vezes, a barreira $2$ é movida 10 vezes, a barreira $3$ é movida 1 vez e a barreira $4$ é movida 7 vezes.

Início da fase → primeiro ataque → segundo ataque → terceiro ataque → quarto 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

Saída 2

34
178
13
6
18
0
36