حصلت على لعبة فيديو أصدرتها شركة JOI. كانت لعبة متقنة إلى حد كبير، وكنت تلعبها كل يوم مستمتعًا بها.

ذات يوم، ظهرت مرحلة يسميها اللاعبون «الليزر». يبدو أنها شديدة الصعوبة، حتى إن اللاعبين الممتازين لا ينجحون فيها إلا باحتمال ضئيل جدًا. وبعد محاولات عديدة، أدركت أنه قد يكون من الممكن اجتيازها باتخاذ قرارات فائقة السرعة، وفكرت في كتابة برنامج للتعامل معها.

تجري مرحلة الليزر في مكان توجد فيه $N$ حواجز. المكان مستطيل ومقسّم إلى خلايا مربعة أبعادها $1\times1$. تُمثّل كل خلية بزوج $(x,y)$ من عددين صحيحين غير سالبين. الخلية $(0,0)$ هي الخلية في الزاوية السفلية اليسرى، وتمثّل $(x,y)$ الخلية التي تبعد $x$ خلايا إلى اليمين و$y$ خلايا إلى الأعلى عن $(0,0)$.

عند بدء المرحلة يظهر عدو ويشن هجماته. تحدث $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$ هجمات.
• يحتوي السطر رقم $i$ ($1\le i\le N$) من الأسطر الـ$N$ التالية على عددين صحيحين مفصولين بمسافة: $A_i,B_i$. وهذا يعني أن الحاجز $i$ يشغل عند بدء المرحلة الخلايا من $(A_i,i)$ إلى $(B_i,i)$.
• يحتوي السطر رقم $j$ ($1\le j\le M$) من الأسطر الـ$M$ التالية على عدد صحيح $P_j$. وهذا يعني أن العدو في الهجوم رقم $j$ يطلق شعاع ليزر مستقيمًا من $(P_j,N+1)$ نحو $(P_j,0)$.

الإخراج

اكتب $N$ سطرًا في الإخراج القياسي. في السطر رقم $i$ ($1\le i\le N$)، اكتب أقل عدد من الحركات للحاجز $i$.

القيود

تستوفي جميع بيانات الإدخال الشروط التالية.

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

المهام الفرعية

المهمة الفرعية 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$ ثلاث مرات إلى اليمين، والحاجز $2$ مرتين إلى اليمين، ولا تحرّك الحاجز $3$، وحرّك الحاجز $4$ مرتين إلى اليسار.
• قبل الهجوم الثاني، لا تحرّك الحاجز $1$، وحرّك الحاجز $2$ مرتين إلى اليسار، ولا تحرّك الحاجز $3$، وحرّك الحاجز $4$ مرتين إلى اليسار.
• قبل الهجوم الثالث، لا تحرّك الحاجز $1$، وحرّك الحاجز $2$ مرة واحدة إلى اليسار، ولا تحرّك الحاجز $3$، وحرّك الحاجز $4$ مرة واحدة إلى اليسار.
• قبل الهجوم الرابع، حرّك الحاجز $1$ مرتين إلى اليمين، والحاجز $2$ خمس مرات إلى اليمين، والحاجز $3$ مرة واحدة إلى اليمين، والحاجز $4$ مرتين إلى اليمين.

بهذه الطريقة يتحرك الحاجز $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