1052 : Domino
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
มีโดมิโน N ชิ้นวางเรียงอยู่บนเส้นแนวแกน x ที่วางตามแนวซ้าย-ขวา  จุดปลายด้านซ้ายของเส้นถือว่ามีพิกัดในแกน x เท่ากับ 0    เราจะเรียกโดมิโนเรียงตามลำดับจากปลายด้านซ้ายไปยังปลายด้านขวา  โดยเริ่มจากชิ้นที่ 1 ไปจนถึงชิ้นที่ N   โดมิโนชิ้นที่ I  มีความสูง HI และวางอยู่บนเส้นที่มีพิกัดแกน x เท่ากับ XI  ตัวอย่างการวาง (ในแนวด้านข้าง) แสดงดังรูป



ในการเล่นโดมิโนนั้น  เราจะเลือกโดมิโนตัวแรกแล้วผลักไปทางด้านซ้ายหรือทางด้านขวาก็ได้  ถ้าโดมิโน “ล้ม” ไปโดนโดมิโนตัวใด  ตัวที่ถูกล้มโดนจะล้มไปชนตัวอื่น ๆ ด้วย   โดมิโนสามารถล้มออกไปนอกขอบของเส้นตรงด้านล่างได้

อย่างไรก็ตาม เราถือว่าโดมิโนไม่มีความหนา  ดังนั้นถ้าล้มไปแล้วปลายโดมิโนไปสัมผัสอีกตัวหนึ่งพอดี จะไม่มีการล้มต่อ  ยกตัวอย่างเช่น ถ้ามีโดมิโนความสูง 1 หน่วยอยู่ที่ตำแหน่ง 10  และมีโดมิโนอีกชิ้นอยู่ที่ตำแหน่ง 11 ถ้าโดมิโนความสูง 1 หน่วย ถูกทำให้ล้มไปทางด้านขวา  โดมิโนที่อยู่ที่ตำแหน่ง 11 จะไม่ล้มไปด้วย เพราะว่าไม่มีการชน (โดมิโนที่ล้มลงมาสัมผัสอีกอันพอดี)

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

ข้อมูลนำเข้า
บรรทัดแรก ระบุจำนวนเต็ม N (1 <= N <= 100,000)  จากนั้นอีก N บรรทัดจะระบุข้อมูลของโดมิโนแต่ละอัน  กล่าวคือ บรรทัดที่ 1 + I  จะระบุจำนวนเต็มสองจำนวน  XI  HI   (1 <= XI <= 1,000,000,000; 1 <= HI <= 1,000,000,000)  รับประกันว่า  0 <= XI < XI+1  สำหรับทุก ๆ  1 <= I < N

ข้อมูลส่งออก
มีบรรทัดเดียว ประกอบไปด้วยจำนวนเต็ม J  และอักขระ D   โดยที่ J คือหมายเลขของโดมิโนที่ถ้าเราเริ่มผลัก และอักขระ D จะเป็นค่า L หรือ R เพื่อระบุทิศทางในการผลัก โดยที่ L แทนการผลักไปทางซ้าย และ R แทนการผลักไปทางขวา  ถ้ามีโดมิโนหลายชิ้นที่พลักได้จำนวนเท่ากัน ให้ตอบตัวที่มีหมายเลขน้อยที่สุด  และในกรณีที่พิจารณาโดมิโนตัวที่มีหมายเลยน้อยที่สุดแล้วผลักได้ทั้งสองทิศทาง ให้ตอบการผลักไปทางซ้าย

ข้อมูลชุดทดสอบ
ไม่น้อยกว่า 20% ของข้อมูลชุดทดสอบมี N <= 1000

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

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

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

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