Baltic2013

Ball Machine

เรามีเครื่องจักรลูกบอล (ball machine) ที่สามารถพิจารณาว่าเป็น rooted tree ได้ โหนดใน tree ดังกล่าวจะมีหมายเลขตั้งแต่ 1 ถึง N แต่ละโหนดอาจจะว่างหรือมีลูกบอลหนึ่งลูก เมื่อเริ่มต้น ทุกโหนดอยู่ในสถานะว่าง ขณะที่ทำงาน เครื่องจักรจะสามารถทำงานตามการดำเนินการได้สองแบบ คือ:

แบบที่ 1. เพิ่มลูกบอล k ลูกเข้าใน ball machine: ลูกบอลจะถูกใส่ทีละลูกที่โหนด root ถ้าลูกบอลมีโหนดที่ว่างที่ติดกันด้านล่าง ลูกบอลจะไหลลงไปที่โหนดนั้น ถ้ามีโหนดลูกที่ว่างหลายโหนด ลูกบอลจะเลือกโหนดที่มีโหนดหมายเลขน้อยที่สุดในต้นไม้ย่อยที่มีโหนดนั้นเป็น root

ถ้าลูกบอลไหลลงไปหลาย ๆ ระดับ ลูกบอลจะเลือกโหนดลูกตามเงื่อนไขดังกล่าวในทุก ๆ ระดับ

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

แบบที่ 2. นำลูกบอลออกจากบางโหนด: โหนดนั้นจะเปลี่ยนสถานะเป็นว่าง จากนั้นลูกบอลที่อยู่ด้านบน (ถ้ามี) ก็จะไหลลงมา เมื่อใดที่โหนดพ่อแม่ของโหนดที่ว่างมีลูกบอล ลูกบอลจะไหลลงไปยังโหนดนั้น

ถ้าเรานำลูกบอลออกจากโหนด 5, 7, และ 8 (ตามลำดับดังกล่าว) จากเครื่องจักรในรูปด้านล่าง โหนด 1, 2, และ 3 จะเปลี่ยนสถานะเป็นโหนดว่าง

Input

• บรรทัดแรกระบุจำนวนเต็ม N และ Q แทนจำนวนโหนดและจำนวนการดำเนินการ

• อีก N บรรทัดหลังจากนั้นเป็นข้อมูลอธิบายเครื่องจักร แต่ละบรรทัดจะระบุจำนวนเต็มหนึ่งจำนวน เป็นหมายเลขของโหนด กล่าวคือ ในบรรทัดที่ i ของกลุ่มบรรทัดเหล่านี้จะระบุหมายเลขของโหนดพ่อแม่ของโหนดที่ i, หรือค่า 0 ถ้าโหนด i เห็นโหนด root ของต้นไม้ดังกล่าว

• อีกแต่ละ Q บรรทัดถัดจากนั้นจะมีจำนวนเต็มสองจำนวนที่ระบุการดำเนินการ การดำเนินการแบบที่ 1 จะระบุด้วยบรรทัดในรูปแบบ 1 k โดยที่ k แทนจำนวนของลูกบอลที่จะใส่เข้าไปในเครื่องจักร สำหรับการดำเนินการแบบที่ 2 จะระบุด้วยบรรทัดในรูปแบบ 2 x โดยที่ x แทนหมายเลขของโหนดที่จะนำลูกบอลออก รับประกันว่าการดำเนินการต่าง ๆ นั้นถูกต้อง กล่าวคือ จะไม่มีการเพิ่มลูกบอลมากกว่าจำนวนโหนดว่างในเครื่องและจะไม่มีการนำลูกบอลออกจากโหนดที่ว่าง

Output

สำหรับการดำเนินการประเภทที่ 1 ให้พิมพ์หมายเลขของโหนดสุดท้ายที่ลูกบอลลูกสุดท้ายที่ใส่ไปไปตกอยู่ สำหรับการดำเนินการประเภทที่ 2 ให้พิมพ์จำนวนลูกบอลที่ไหลลงมาหลังจากการนำลูกบอลออกจากโหนดที่ระบุ

ข้อจำกัด

• N,Q <= 100 000
• ในข้อมูลทดสอบที่มีคะแนน 25 คะแนน แต่ละโหนดจะมี 0 หรือ 2 โหนด นอกจากนี้ ทุก ๆ โหนดที่ไม่มีลูกจะมีระยะทางจากโหนด root เท่ากันทั้งหมด
• ในข้อมูลทดสอบที่มีคะแนน 30 คะแนน แต่ละการดำเนินการจะถูกเรียกโดยรับประกันว่าจะไม่มีลูกบอลไหลลงมาหลังจากการดำเนินการที่ 2
• ในข้อมูลทดสอบที่มีคะแนน 40 คะแนน จะมีการทำงานตามดำเนินการประเภทที่ 1 แค่ครั้งเดียว และจะเป็นกิจกรรมแรกเท่านั้น
• เซตของข้อมูลทดสอบทั้ง 3 เซตที่กล่าวมานั้น pairwise disjoint กัน