1140 : หุ่นยนต์ (robot)
Problem type : Batch
Time limit : 3.0 second(s)
Memory limit : 32 megabyte(s)
มีเสา N ต้น ตั้งอยู่ในสนาม เสาแต่ละต้นจะมีหมายเลขกำกับตั้งแต่ 1, 2, 3 เรียงไปเรื่อยๆ จนถึง N

คุณได้ประดิษฐ์หุ่นยนต์ตัวหนึ่งที่มีคุณสมบัติว่า เมื่อนำหุ่นยนต์ดังกล่าวไปปล่อยไว้ในสนาม หุ่นยนต์จะเดินเป็นเส้นตรงไปหาเสาที่อยู่ใกล้ที่สุด (วัดจากตำแหน่งปัจจุบันของหุ่นยนต์) ที่มันยังไม่เคยไปถึง (หากมีเสามากกว่า 1 ต้นที่อยู่ใกล้ที่สุดเท่ากันพอดี หุ่นยนต์จะเลือกเดินไปหาเสาที่มีหมายเลขน้อยที่สุด) และเมื่อเดินไปถึงเสาต้นนั้นแล้ว ก็จะเดินต่อไปหาเสาที่อยู่ใกล้ที่สุดที่มันยังไม่เคยไปถึงต่อไปเรื่อยๆ จนกระทั่งไปถึงเสาครบทุกต้น ก็จะหยุดเดิน

งานของคุณ
จงเขียนโปรแกรมเพื่อรับตำแหน่งของเสาแต่ละต้น แล้วตอบคำถามทั้งหมด Q คำถามว่า หากเริ่มปล่อยหุ่นยนต์ที่พิกัด (X, Y) เสาหมายเลข K จะเป็นเสาลำดับที่เท่าไรที่หุ่นยนต์เดินไปถึง

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ Q (1 ≤ N ≤ 1,000; 1 ≤ Q ≤ 100,000) แทนจำนวนเสาในสนาม และจำนวนคำถาม

อีก N บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ N) ระบุจำนวนเต็ม Xi และ Yi (1 ≤ Xi,Yi ≤ 10,000) แทนพิกัดตามแกน X และแกน Y ของเสาหมายเลข i

อีก Q บรรทัดต่อมา ในบรรทัดที่ i+N+1 (1 ≤ i ≤ Q) ระบุจำนวนเต็ม X, Y และ K (1 ≤ X,Y ≤ 10,000; 1 ≤ K ≤ N) แสดงถึงคำถามที่ i

ข้อมูลส่งออก
มีทั้งหมด Q บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ N) แสดงคำตอบของคำถามที่ i

การให้คะแนน
20% ของข้อมูลทดสอบ จะมี N ≤ 100 และ Q ≤ 1,000
50% ของข้อมูลทดสอบ จะมี N ≤ 100

ที่มา
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 4
2 2
4 1
5 3
2 1 1
2 1 2
4 4 3
3 4 3		 1
2
1
3
5 5
5 6
2 2
3 1
5 4
3 3
1 1 5
2 1 3
3 1 1
4 3 4
3 3 3		 3
2
5
4
3

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 25 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)