אתם מתכננים לפתוח חנות למכירת בובות מטריושקה. לשם כך הזמנתם ממפעל $N$ בובות מטריושקה, הממוספרות מ-$1$ עד $N$. אפשר להתייחס לבובה מספר $i$ ($1 \le i \le N$) כאל גליל ישר וחלול, שקוטר בסיסו $R_i$ סנטימטרים וגובהו $H_i$ סנטימטרים.

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

יום אחד קיבלתם הודעה מהמפעל שממנו הזמנתם את הבובות. אי אפשר להכין את כל $N$ הבובות בבת אחת, ולכן כל הבובות מבין $N$ הבובות שקוטר בסיסן לפחות $A$ סנטימטרים וגובהן לכל היותר $B$ סנטימטרים יגיעו מראש.

הערכים $A,B$ עלולים להשתנות בהתראה קצרה. לכן החלטתם לחשב מראש, לכל אחד מ-$Q$ הזוגות $(A_j,B_j)$ ($1 \le j \le Q$), את המספר המזערי של בובות שאינן נמצאות בתוך שום בובה אחרת, כאשר מאחסנים זו בתוך זו את הבובות שיגיעו מראש.

משימה

נתונים קוטר הבסיס והגובה של כל בובת מטריושקה, וכן $Q$ זוגות $(A_j,B_j)$ ($1 \le j \le Q$). כתבו תוכנית שמחשבת עבור כל זוג את המספר המזערי של בובות שאינן נמצאות בתוך שום בובה אחרת, כאשר מאחסנים זו בתוך זו את הבובות שיגיעו מראש.

קלט

קראו את הנתונים הבאים מהקלט התקני.

• השורה הראשונה מכילה את המספרים השלמים $N,Q$, מופרדים ברווח. משמעותם היא שהוזמנו $N$ בובות מטריושקה, ונתונים $Q$ זוגות ערכים של $A,B$.
• השורה ה-$i$ ($1 \le i \le N$) מבין $N$ השורות הבאות מכילה את המספרים השלמים $R_i,H_i$, מופרדים ברווח. משמעותם היא שקוטר הבסיס של הבובה ה-$i$ הוא $R_i$ סנטימטרים וגובהה $H_i$ סנטימטרים.
• השורה ה-$j$ ($1 \le j \le Q$) מבין $Q$ השורות הבאות מכילה את המספרים השלמים $A_j,B_j$, מופרדים ברווח.

פלט

הפלט מורכב מ-$Q$ שורות. בשורה ה-$j$ ($1 \le j \le Q$) הדפיסו עבור הזוג $(A_j,B_j)$ את המספר המזערי של בובות שאינן נמצאות בתוך שום בובה אחרת, כאשר מאחסנים זו בתוך זו את הבובות שיגיעו מראש.

מגבלות

כל נתוני הקלט מקיימים את התנאים הבאים.

• $1 \le N \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $1 \le R_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le A_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).

תתי־משימות

תת־משימה 1 [11 נקודות]

מתקיימים התנאים הבאים.

• $N \le 10$.
• $Q=1$.

תת־משימה 2 [15 נקודות]

מתקיימים התנאים הבאים.

• $N \le 100$.
• $Q=1$.

תת־משימה 3 [25 נקודות]

מתקיימים התנאים הבאים.

• $N \le 2\,000$.
• $Q \le 2\,000$.

תת־משימה 4 [49 נקודות]

אין מגבלות נוספות.

דוגמאות

קלט 1

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

פלט 1

0
1
2

הסבר

• כאשר $(A,B)=(10,5)$, אין אף בובת מטריושקה שקוטר בסיסה לפחות $10$ סנטימטרים וגובהה לכל היותר $5$ סנטימטרים, ולכן מדפיסים $0$.
• כאשר $(A,B)=(3,5)$, יגיעו הבובות שקוטר בסיסן לפחות $3$ סנטימטרים וגובהן לכל היותר $5$ סנטימטרים, כלומר בובות מספר $1$ ו-$7$. אפשר להכניס את בובה מספר $7$ לתוך בובה מספר $1$. המספר המזערי של בובות שאינן נמצאות בתוך שום בובה אחרת הוא $1$.
• כאשר $(A,B)=(3,9)$, יגיעו הבובות שקוטר בסיסן לפחות $3$ סנטימטרים וגובהן לכל היותר $9$ סנטימטרים, כלומר בובות מספר $1,2,3,7$. במקרה זה אפשר להכניס את בובה מספר $7$ לתוך בובה מספר $1$, ואת בובה מספר $1$ לתוך בובה מספר $3$. המספר המזערי של בובות שאינן נמצאות בתוך שום בובה אחרת הוא $2$.

קלט 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

פלט 2

3
1
3
5
0
2
1
3