تعتزم فتح متجر لبيع دمى الماتريوشكا، ولذلك طلبت من المصنع $N$ دمية. هذه الدمى مرقمة من $1$ إلى $N$. يمكن اعتبار الدمية رقم $i$ ($1 \le i \le N$) أسطوانة دائرية قائمة مجوفة، قطر قاعدتها $R_i$ سنتيمترًا وارتفاعها $H_i$ سنتيمترًا.

يمكن تخزين دمى الماتريوشكا بإدخال بعضها داخل بعض. تستطيع كل دمية احتواء دمية أخرى واحدة فقط يكون كل من قطر قاعدتها وارتفاعها أصغر من نظيره في الدمية الحاوية. وقد تحتوي الدمية الموضوعة في الداخل بدورها على دمية أخرى.

ذات يوم، وصلتك رسالة من المصنع الذي طلبت منه الدمى. لا يستطيع المصنع تجهيز الدمى الـ$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