השגתם משחק וידאו שהוציאה חברת JOI. המשחק עשוי היטב, ושיחקתם בו מדי יום בהנאה.

יום אחד הופיע שלב המכונה בקרב השחקנים „לייזר“. נראה שזהו שלב קשה ביותר, שאפילו שחקנים מצטיינים מצליחים לעבור רק בהסתברות קטנה מאוד. לאחר ניסיונות רבים, הבנתם שייתכן שאפשר לעבור אותו באמצעות קבלת החלטות מהירה מאוד, וחשבתם שאפשר להתמודד איתו בעזרת תוכנית.

שלב הלייזר מתרחש בזירה שבה מוצבות $N$ חומות מגן. הזירה מלבנית ומחולקת לתאים ריבועיים בגודל $1 \times 1$. כל תא מסומן $(x,y)$ באמצעות מספרים שלמים אי-שליליים $x,y$. התא $(0,0)$ נמצא בפינה השמאלית התחתונה, והתא $(x,y)$ נמצא $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$ פעמים.
• השורה ה-$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 \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$ ימינה 3 פעמים, הזיזו את חומה $2$ ימינה 2 פעמים, אל תזיזו את חומה $3$, והזיזו את חומה $4$ שמאלה 2 פעמים.
• לפני ההתקפה השנייה, אל תזיזו את חומה $1$, הזיזו את חומה $2$ שמאלה 2 פעמים, אל תזיזו את חומה $3$, והזיזו את חומה $4$ שמאלה 2 פעמים.
• לפני ההתקפה השלישית, אל תזיזו את חומה $1$, הזיזו את חומה $2$ שמאלה פעם אחת, אל תזיזו את חומה $3$, והזיזו את חומה $4$ שמאלה פעם אחת.
• לפני ההתקפה הרביעית, הזיזו את חומה $1$ ימינה 2 פעמים, את חומה $2$ ימינה 5 פעמים, את חומה $3$ ימינה פעם אחת ואת חומה $4$ ימינה 2 פעמים.

בדרך זו מזיזים את חומה $1$ 5 פעמים, את חומה $2$ 10 פעמים, את חומה $3$ פעם אחת ואת חומה $4$ 7 פעמים.

תחילת השלב; ההתקפה הראשונה; ההתקפה השנייה; ההתקפה השלישית; ההתקפה הרביעית.

קלט 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