Du har fått tak i et videospill utgitt av JOI Corp. Det er et vellaget spill, og du har spilt det hver dag med stor glede.

En dag dukket et brett kalt «Laser» opp blant spillerne. Det virker som dette brettet er ekstremt vanskelig, og det sies at selv dyktige spillere bare klarer det med en svært liten sannsynlighet. Mens du prøvde deg på brettet mange ganger, innså du at det er en mulighet for å klare det ved å ta veldig raske avgjørelser, og du tenkte at du kanskje kunne håndtere det ved å lage et program.

Laserbrettet foregår på et sted der det er plassert $N$ vegger. Brettet er rektangulært og er delt inn i $1 \times 1$ kvadratiske ruter. Hver rute representeres av $(x, y)$ ved hjelp av heltall $x, y \ge 0$. $(0, 0)$ er ruten i nederste venstre hjørne, og $(x, y)$ representerer ruten $x$ ruter til høyre og $y$ ruter opp fra $(0, 0)$.

Når brettet starter, dukker fiender opp og angriper. $M$ angrep utføres etter hverandre. I det $j$-te angrepet skyter fienden en laser rett fra ruten $(P_j, N+1)$ mot ruten $(P_j, 0)$.

Hver vegg er plassert på flere påfølgende ruter med samme $y$-koordinat. Vegg $i$ ($1 \le i \le N$) er et rektangel med en horisontal bredde på $B_i - A_i + 1$ og en vertikal bredde på $1$. Ved starten av brettet opptar den rutene fra $(A_i, i)$ til $(B_i, i)$. Du kan flytte veggene horisontalt så mange ganger du vil, både før fiendens første angrep og mellom hvilke som helst to fiendeangrep. I ett trekk kan du flytte én vegg én rute til høyre eller én rute til venstre.

Når en laser treffer en vegg, svekkes kraften dens. Du ønsker å minimere kraften til laseren ved å flytte veggene slik at laseren treffer alle veggene.

På dette brettet ønsker du å minimere det totale antallet veggbevegelser.

Oppgave

Gitt startposisjonene til veggene og posisjonene til fiendens angrep, beregn det minste antallet bevegelser for hver vegg for å sikre at hver laser treffer hver vegg.

Inndata

Les følgende data fra standard inndata:

• Den første linjen inneholder to mellomromseparerte heltall $N$ og $M$. Dette angir at det er $N$ vegger på dette brettet og at $M$ angrep vil bli utført.
• Den $i$-te linjen av de neste $N$ linjene ($1 \le i \le N$) inneholder to mellomromseparerte heltall $A_i$ og $B_i$. Dette angir at ved starten av brettet er vegg $i$ plassert fra rute $(A_i, i)$ til rute $(B_i, i)$.
• Den $j$-te linjen av de neste $M$ linjene ($1 \le j \le M$) inneholder et heltall $P_j$. Dette angir at i det $j$-te angrepet skyter fienden en laser rett fra rute $(P_j, N+1)$ mot rute $(P_j, 0)$.

Utdata

Skriv ut $N$ linjer til standard utdata. Den $i$-te linjen ($1 \le i \le N$) skal inneholde det minste antallet bevegelser for vegg $i$.

Begrensninger

Alle inndata oppfyller følgende betingelser:

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

Deloppgaver

Deloppgave 1 [10 poeng]

• $N = 1$ er oppfylt.

Deloppgave 2 [45 poeng]

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

Deloppgave 3 [45 poeng]

• Det er ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

5
10
1
7

Forklaring

I disse inndataene er én måte å minimere antallet veggbevegelser på som følger:

• Før det 1. angrepet: flytt vegg 1 til høyre 3 ganger, flytt vegg 2 til høyre 2 ganger, ikke flytt vegg 3, og flytt vegg 4 til venstre 2 ganger.
• Før det 2. angrepet: ikke flytt vegg 1, flytt vegg 2 til venstre 2 ganger, ikke flytt vegg 3, og flytt vegg 4 til venstre 2 ganger.
• Før det 3. angrepet: ikke flytt vegg 1, flytt vegg 2 til venstre 1 gang, ikke flytt vegg 3, og flytt vegg 4 til venstre 1 gang.
• Før det 4. angrepet: flytt vegg 1 til høyre 2 ganger, flytt vegg 2 til høyre 5 ganger, flytt vegg 3 til høyre 1 gang, og flytt vegg 4 til høyre 2 ganger.

På denne måten flyttes vegg 1 totalt 5 ganger, vegg 2 flyttes 10 ganger, vegg 3 flyttes 1 gang og vegg 4 flyttes 7 ganger.

Starten av brettet

1. angrep

2. angrep

3. angrep

4. angrep

Inndata 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