Сіз JOI корпорациясы шығарған бейнеойын бағдарламасын қолға түсірдіңіз. Бұл өте жақсы жасалған ойын болғандықтан, оны күн сайын қызыға ойнап жүрсіз.

Бір күні ойыншылар арасында «Лазер» деп аталатын кезең пайда болды. Бұл кезең өте қиын көрінеді, тіпті үздік ойыншылардың өзі оны өте аз ықтималдықпен ғана өте алады деседі. Кезеңді бірнеше рет ойнап көріп, сіз өте жылдам шешім қабылдау арқылы одан өту мүмкіндігі бар екенін түсіндіңіз және программа жазу арқылы оны еңсеруге болады деп ойладыңыз.

Лазер кезеңі $N$ қабырға орналасқан жерде өтеді. Кезең тікбұрышты пішінді және $1 \times 1$ шаршы ұяшықтарға бөлінген. Әрбір ұяшық $x, y \ge 0$ бүтін сандары арқылы $(x, y)$ түрінде беріледі. $(0, 0)$ — сол жақ төменгі бұрыштағы ұяшық, ал $(x, y)$ — $(0, 0)$ ұяшығынан оңға қарай $x$ ұяшық және жоғары қарай $y$ ұяшық жерде орналасқан ұяшық.

Кезең басталғанда жаулар пайда болып, шабуыл жасайды. Тізбектей $M$ шабуыл орындалады. $j$-ші шабуылда жау $(P_j, N+1)$ ұяшығынан $(P_j, 0)$ ұяшығына қарай түзу сызық бойымен лазер атады.

Әрбір қабырға $y$-координатасы бірдей бірнеше қатар орналасқан ұяшықтарда жатыр. $i$-ші қабырға ($1 \le i \le N$) — көлденең ені $B_i - A_i + 1$ және тік биіктігі $1$ болатын тікбұрыш. Кезеңнің басында ол $(A_i, i)$ ұяшығынан $(B_i, i)$ ұяшығына дейінгі орындарды алып жатады. Сіз қабырғаларды жаудың бірінші шабуылына дейін де, кез келген екі шабуылдың арасында да көлденең бағытта қалағаныңызша жылжыта аласыз. Бір жүрісте бір қабырғаны бір ұяшық оңға немесе бір ұяшық солға жылжытуға болады.

Лазер қабырғаға тиген кезде оның қуаты әлсірейді. Сіз лазер барлық қабырғаларға тиетіндей етіп қабырғаларды жылжыту арқылы лазердің қуатын барынша азайтқыңыз келеді.

Бұл кезеңде сіз қабырғалардың жалпы қозғалыс санын барынша азайтқыңыз келеді.

Тапсырма

Қабырғалардың бастапқы орындары мен жау шабуылдарының орындары берілгенде, әрбір лазер әрбір қабырғаға тиюі үшін әр қабырғаның ең аз қозғалыс санын есептеңіз.

Кіріс форматы

Стандартты енгізуден келесі деректерді оқыңыз:

• Бірінші жолда бос орын арқылы бөлінген екі бүтін сан $N$ және $M$ берілген. Бұл осы кезеңде $N$ қабырға бар екенін және $M$ шабуыл жасалатынын білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бос орын арқылы бөлінген екі бүтін сан $A_i$ және $B_i$ берілген. Бұл кезеңнің басында $i$-ші қабырға $(A_i, i)$ ұяшығынан $(B_i, i)$ ұяшығына дейін орналасқанын білдіреді.
• Келесі $M$ жолдың $j$-ші жолында ($1 \le j \le M$) бір бүтін сан $P_j$ берілген. Бұл $j$-ші шабуылда жау $(P_j, N+1)$ ұяшығынан $(P_j, 0)$ ұяшығына қарай тікелей лазер ататынын білдіреді.

Шығыс форматы

Стандартты шығаруға $N$ жол шығарыңыз. $i$-ші жолда ($1 \le i \le N$) $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$).

Ішкі есептер

Ішкі есеп 1 [10 ұпай]

• $N = 1$ шарты орындалады.

Ішкі есеп 2 [45 ұпай]

• $A_i = 0$ ($1 \le i \le N$) шарты орындалады.

Ішкі есеп 3 [45 ұпай]

• Қосымша шектеулер жоқ.

Мысалдар

Кіріс 1

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

Шығыс 1

5
10
1
7

Ескертпе

Бұл кірісте қабырғалардың қозғалыс санын барынша азайтудың бір жолы келесідей:

• 1-ші шабуылға дейін: 1-ші қабырғаны оңға 3 рет жылжыту, 2-ші қабырғаны оңға 2 рет жылжыту, 3-ші қабырғаны қозғамау және 4-ші қабырғаны солға 2 рет жылжыту.
• 2-ші шабуылға дейін: 1-ші қабырғаны қозғамау, 2-ші қабырғаны солға 2 рет жылжыту, 3-ші қабырғаны қозғамау және 4-ші қабырғаны солға 2 рет жылжыту.
• 3-ші шабуылға дейін: 1-ші қабырғаны қозғамау, 2-ші қабырғаны солға 1 рет жылжыту, 3-ші қабырғаны қозғамау және 4-ші қабырғаны солға 1 рет жылжыту.
• 4-ші шабуылға дейін: 1-ші қабырғаны оңға 2 рет жылжыту, 2-ші қабырғаны оңға 5 рет жылжыту, 3-ші қабырғаны оңға 1 рет жылжыту және 4-ші қабырғаны оңға 2 рет жылжыту.

Осылайша, 1-ші қабырға 5 рет, 2-ші қабырға 10 рет, 3-ші қабырға 1 рет және 4-ші қабырға 7 рет жылжытылады.

Кезеңнің басталуы

1-ші шабуыл

2-ші шабуыл

3-ші шабуыл

4-ші шабуыл

Кіріс 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

Шығыс 2

34
178
13
6
18
0
36