Þú hefur eignast tölvuleik sem gefinn var út af JOI Corp. Þetta er vel gerður leikur og þú hefur spilað hann á hverjum degi með nokkurri ánægju.

Dag einn kom fram borð sem kallast „Leysigeisli“ (Laser) meðal leikmanna. Svo virðist sem þetta borð sé afar erfitt og sagt er að jafnvel frábærir spilarar geti aðeins klárað það með mjög litlum líkum. Þegar þú reyndir við borðið mörgum sinnum áttaðir þú þig á því að mögulegt væri að klára það með því að taka mjög hraðar ákvarðanir, og þú hugsaðir að þú gætir ef til vill ráðið við það með því að búa til forrit.

Leysigeislaborðið gerist á stað þar sem $N$ veggjum hefur verið komið fyrir. Borðið er rétthyrnt og er skipt í $1 \times 1$ ferhyrnda reiti. Hver reitur er táknaður með $(x, y)$ með heiltölum $x, y \ge 0$. $(0, 0)$ er reiturinn í neðra vinstra horninu og $(x, y)$ táknar reitinn sem er $x$ reitum til hægri og $y$ reitum fyrir ofan $(0, 0)$.

Þegar borðið hefst birtast óvinir og gera árás. $M$ árásir eru gerðar í röð. Í $j$-tu árásinni skýtur óvinurinn leysigeisla beint frá reit $(P_j, N+1)$ í átt að reit $(P_j, 0)$.

Hver veggur er staðsettur á nokkrum samliggjandi reitum með sama $y$-hnit. Veggur $i$ ($1 \le i \le N$) er rétthyrningur með lárétta breidd $B_i - A_i + 1$ og lóðrétta breidd $1$. Í upphafi borðsins þekur hann reitina frá $(A_i, i)$ til $(B_i, i)$. Þú getur fært veggina lárétt eins oft og þú vilt, bæði fyrir fyrstu árás óvinarins og á milli hvaða tveggja árása sem er. Í einni færslu getur þú fært einn vegg um einn reit til hægri eða einn reit til vinstri.

Þegar leysigeisli hæfir vegg veikist kraftur hans. Þú vilt lágmarka kraft leysigeislans með því að færa veggina þannig að geislinn hæfi alla veggina.

Í þessu borði viltu lágmarka heildarfjölda veggfærsla.

Verkefni

Þegar upphafsstaðsetningar veggjanna og staðsetningar árása óvinarins eru gefnar, reiknið út lágmarksfjölda færsla fyrir hvern vegg til að tryggja að sérhver leysigeisli hæfi sérhvern vegg.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $M$ aðskildar með bili. Þetta gefur til kynna að það séu $N$ veggir í þessu borði og að $M$ árásir verði gerðar.
• $i$-ta línan af næstu $N$ línum ($1 \le i \le N$) inniheldur tvær heiltölur $A_i$ og $B_i$ aðskildar með bili. Þetta gefur til kynna að í upphafi borðsins sé veggur $i$ staðsettur frá reit $(A_i, i)$ til reits $(B_i, i)$.
• $j$-ta línan af næstu $M$ línum ($1 \le j \le M$) inniheldur heiltölu $P_j$. Þetta gefur til kynna að í $j$-tu árásinni skjóti óvinurinn leysigeisla beint frá reit $(P_j, N+1)$ í átt að reit $(P_j, 0)$.

Úttak

Skrifið út $N$ línur í staðalúttak. $i$-ta línan ($1 \le i \le N$) á að innihalda lágmarksfjölda færsla fyrir vegg $i$.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

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

Undirverkefni

Undirverkefni 1 [10 stig]

• $N = 1$ gildir.

Undirverkefni 2 [45 stig]

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

Undirverkefni 3 [45 stig]

• Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

5
10
1
7

Skýring

Í þessu inntaki er ein leið til að lágmarka fjölda veggfærsla eftirfarandi:

• Fyrir 1. árás: færa vegg 1 til hægri 3 sinnum, færa vegg 2 til hægri 2 sinnum, ekki færa vegg 3 og færa vegg 4 til vinstri 2 sinnum.
• Fyrir 2. árás: ekki færa vegg 1, færa vegg 2 til vinstri 2 sinnum, ekki færa vegg 3 og færa vegg 4 til vinstri 2 sinnum.
• Fyrir 3. árás: ekki færa vegg 1, færa vegg 2 til vinstri 1 sinni, ekki færa vegg 3 og færa vegg 4 til vinstri 1 sinni.
• Fyrir 4. árás: færa vegg 1 til hægri 2 sinnum, færa vegg 2 til hægri 5 sinnum, færa vegg 3 til hægri 1 sinni og færa vegg 4 til hægri 2 sinnum.

Á þennan hátt er veggur 1 færður 5 sinnum, veggur 2 er færður 10 sinnum, veggur 3 er færður 1 sinni og veggur 4 er færður 7 sinnum.

Upphaf borðs

1. árás

2. árás

3. árás

4. árás

Inntak 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

Úttak 2

34
178
13
6
18
0
36