คุณกำลังจะเปิดร้านขายตุ๊กตา Matryoshka จึงสั่งตุ๊กตา Matryoshka จำนวน $N$ ตัวจากโรงงาน ตุ๊กตาเหล่านี้มีหมายเลขตั้งแต่ $1$ ถึง $N$ ตุ๊กตาตัวที่ $i$ ($1 \le i \le N$) สามารถมองเป็นทรงกระบอกตรงที่ภายในกลวง มีเส้นผ่านศูนย์กลางฐาน $R_i$ ซม. และสูง $H_i$ ซม.

ตุ๊กตา Matryoshka สามารถเก็บโดยซ้อนตัวหนึ่งไว้ภายในอีกตัวหนึ่งได้ ตุ๊กตาแต่ละตัวสามารถบรรจุตุ๊กตาอื่นได้เพียงหนึ่งตัว ซึ่งต้องมีทั้งเส้นผ่านศูนย์กลางฐานและความสูงน้อยกว่าของตนอย่างเคร่งครัด ตุ๊กตาที่ถูกบรรจุอยู่นั้นอาจบรรจุตุ๊กตาอื่นอยู่ภายในด้วยก็ได้

วันหนึ่ง โรงงานที่คุณสั่งตุ๊กตาติดต่อมา เนื่องจากไม่สามารถเตรียมตุ๊กตาที่สั่งทั้ง $N$ ตัวพร้อมกันได้ จึงจะส่งตุ๊กตาทุกตัวที่มีเส้นผ่านศูนย์กลางฐานอย่างน้อย $A$ ซม. และสูงไม่เกิน $B$ ซม. มาให้ล่วงหน้า จากตุ๊กตาทั้ง $N$ ตัว

ค่า $A,B$ อาจเปลี่ยนแปลงอย่างกะทันหัน ดังนั้น สำหรับแต่ละคู่จากทั้งหมด $Q$ คู่ $(A_j,B_j)$ ($1 \le j \le Q$) คุณจึงตัดสินใจคำนวณล่วงหน้าว่า เมื่อเก็บตุ๊กตาที่ส่งมาล่วงหน้าโดยซ้อนกันแล้ว จำนวนตุ๊กตาที่ไม่ได้อยู่ภายในตุ๊กตาตัวใดเลยมีค่าน้อยที่สุดเท่าใด

งาน

กำหนดข้อมูลเส้นผ่านศูนย์กลางฐานและความสูงของตุ๊กตาแต่ละตัว และคู่ $(A_j,B_j)$ จำนวน $Q$ คู่ ($1 \le j \le Q$) จงเขียนโปรแกรมหาจำนวนตุ๊กตาที่ไม่ได้อยู่ภายในตุ๊กตาตัวใดเลยให้น้อยที่สุด สำหรับแต่ละคู่ เมื่อเก็บตุ๊กตาที่ส่งมาล่วงหน้าโดยซ้อนกัน

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากข้อมูลนำเข้ามาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N,Q$ คั่นด้วยช่องว่าง หมายความว่าคุณสั่งตุ๊กตา Matryoshka จำนวน $N$ ตัว และกำหนดคู่ค่า $A,B$ มาให้ $Q$ คู่
• บรรทัดที่ $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