1049 : Runner
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
นักวิ่ง N คน วิ่งแข่งกันในสนามที่มีลู่วิ่ง M ลู่ ก่อนการแข่งขันจะเริ่มต้น นักวิ่งจะทยอยไปยืนรออยู่ที่ลู่วิ่งโดยจะยืนรอกันตามลำดับที่เดินเข้ามาในสนาม  ในการยืนรอนี้ ไม่จำเป็นที่จำนวนนักวิ่งในแต่ละลู่ต้องเท่ากัน  เมื่อนักวิ่งยืนที่ลู่ครบทุกคนแล้ว การแข่งจะเริ่มขึ้น  โดยจะแบ่งเป็นรอบ ๆ   ในรอบที่ 1 นักวิ่งที่ยืนอยู่เป็นอันดับแรกของแต่ละลู่วิ่งจะวิ่งแข่งกัน  คนที่มีความเร็วสูงที่สุดจะเป็นผู้ชนะ  จากนั้นในรอบถัดมา นักวิ่งคนถัดไปของทุกลู่วิ่งจะวิ่ง  การแข่งขันจะดำเนินไปเรื่อย  ๆ จนกระทั่งนักวิ่งทุกคนออกวิ่ง

ให้เขียนโปรแกรมรับข้อมูลการเดินเข้าลู่วิ่งของนักวิ่งแต่ละคน พร้อมด้วยอัตราเร็วในการวิ่ง  จากนั้นให้โปรแกรมคำนวณหาผู้ชนะในการวิ่งแต่ละรอบจนครบทุกรอบ

ข้อมูลนำเข้า
ให้อ่านข้อมูลจาก standard input  ข้อมูลในบรรทัดแรกประกอบด้วยจำนวนเต็ม N และ M  (1 <= N <= 100,000; 1 <= M <= 10,000)  จากนั้นอีก N บรรทัดจะเป็นข้อมูลการเดินเข้าสนามและความเร็วของนักวิ่งแต่ละคน  กล่าวคือ ในบรรทัดที่ 1 + i  จะเป็นข้อมูลของนักวิ่งที่เดินเข้าสนามมาเป็นลำดับที่ i  บรรทัดดังกล่าวประกอบไปด้วยจำนวนเต็ม Ai Li Si   โดยที่ Ai คือหมายเลขของนักแข่งซึ่งจะไม่ซ้ำกัน  Li แทนหมายเลขลู่ที่เขาเดินไปรอ และ Si แทนความเร็วของนักวิ่ง  (1<= Ai <= 1,000,000; 1<= Li <= M; 1<= Si <= 1,000,000)

ข้อมูลส่งออก
แสดงออกทาง standard output  ผลลัพธ์จะมีจำนวนบรรทัดเท่ากับจำนวนรอบของการแข่งขัน ในแต่ละบรรทัด j ให้พิมพ์หมายเลขของนักวิ่งที่ชนะในรอบที่ j  นักวิ่งที่ชนะในรอบที่ j คือคนที่มีอัตราเร็วสูงสุดที่วิ่งในรอบนั้น  ถ้านักวิ่งที่มีอัตราเร็วมากที่สุดมีมากกว่าหนึ่งคน ให้ตอบคนที่อยู่ในลู่วิ่งที่มีหมายเลขน้อยที่สุด

ข้อมูลชุดทดสอบ
ใน 30% ของข้อมูลชุดทดสอบ N <= 100; M<= 100

ที่มา: สอบปฏิบัติ ครั้งที่ 1 ค่ายคัดเลือกผู้แทนประเทศไทย ไปแข่งขันคอมพิวเตอร์โอลิมปิกระหว่างประเทศ ปี 2550 ค่ายที่ 1

รูปประกอบตัวอย่างข้อมูลนำเข้า

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

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

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