ในการแสดงขับรถผาดโผนบนถนนที่มีเลนทั้งหมด m เลน โดยให้หมายเลขประจำเลนจากซ้ายไปขวามีค่าตั้งแต่ 1 จนถึง m ตามลำดับ นักแสดงขับรถผาดโผนต้องบังคับรถให้แล่นไปบนถนนดังกล่าวให้ปลอดภัยตลอดระยะเวลา t หน่วย การแสดงเริ่มต้น ณ เวลา t = 0 นักแสดงขับรถผาดโผนอยู่ในเลนที่ n

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

จงเขียนโปรแกรมเพื่อบังคับให้รถแล่นไปตามเส้นทางนี้โดยปลอดภัย โดยชุดข้อมูลทดสอบจะมีคำตอบที่ถูกต้องเพียง 1 คำตอบเสมอ

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

1.       บรรทัดแรกระบุจำนวนเลน m โดยที่ 2 ≤ m ≤ 40

2.       บรรทัดที่สองระบุหมายเลขเลนเริ่มต้น n โดยที่ 1 ≤ n ≤ m

3.       บรรทัดที่สามระบุระยะเวลา t โดยที่ 1 ≤ t ≤ 100

4.      บรรทัดที่สี่ถึงบรรทัดที่ t + 3 แสดงสถานะของถนน ณ เวลา 1,2,...,t ตามลำดับ แต่ละบรรทัดระบุตัวเลข m ตัว เลขแต่ละตัวแสดงสถานะของถนน ตั้งแต่เลนที่ 1 ถึงเลนที่ m โดยเลข 0 หมายถึงเลนนั้นไม่มีสิ่งกีดขวาง และเลข 1 หมายถึงมีสิ่งกีดขวางอยู่

ข้อมูลส่งออก

มีอยู่ t บรรทัด แต่ละบรรทัดมีตัวเลข 1 ตัวเพื่อแสดงถึงทางเลือกในการบังคับรถของนักแสดงขับรถผาดโผนในแต่ละช่วงเวลา บรรทัดที่ i หมายถึงการเปลี่ยนเลนจากเวลาที่ i −1 ไปยังเวลาที่ i เมื่อ i =1,2,…,t โดยที่เลข 1 จะหมายถึงขับไปทางซ้าย 1 เลน, เลข 2 หมายถึงขับไปทางขวา 1 เลน, และเลข 3 หมายถึงขับอยู่ในเลนเดิม


ที่มา : การแข่งขันคอมพิวเตอร์โอลิมปิกระดับชาติครั้งที่ 7 (NUTOI7)