Anatoly Cheng McDougal เป็นนักศึกษาทั่วไปในหลายแง่มุม เมื่อใดที่ทำได้ เขาจะพยายามคัดลอกและวางโค้ดแทนการเขียนใหม่ตั้งแต่ต้น วิธีนี้ย่อมทำให้เกิดปัญหา ตัวอย่างเช่น เมื่อเขาเพิ่งเรียนรู้การท่องต้นไม้แบบพรีออร์เดอร์ อินออร์เดอร์ และโพสต์ออร์เดอร์ และได้รับโค้ดพิมพ์ต้นไม้แบบพรีออร์เดอร์ (แสดงทางซ้ายด้านล่าง) เขาก็เพียงคัดลอกและวางโค้ด ย้ายคำสั่งพิมพ์ไปยังตำแหน่งที่ถูกต้อง แล้วเปลี่ยนชื่อกระบวนงาน แต่เขาลืมเปลี่ยนชื่อในการเรียกกระบวนงานภายในโค้ด จึงเกิดโค้ดพิมพ์แบบอินออร์เดอร์และโพสต์ออร์เดอร์ที่ผิดดังแสดงด้านล่าง

void prePrint(TNode t)
{
  output(t.value);
  if (t.left != null)
    prePrint(t.left);
  if (t.right != null)
    prePrint(t.right);
}

void inPrint(TNode t)
{
  if (t.left != null)
    prePrint(t.left);
  output(t.value);
  if (t.right != null)
    prePrint(t.right);
}

void postPrint(TNode t)
{
  if (t.left != null)
    prePrint(t.left);
  if (t.right != null)
    prePrint(t.right);
  output(t.value);
}

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

อาจารย์ของ Anatoly ทดสอบโค้ดกับต้นไม้ตัวอักษรที่สุ่มขึ้นมา เมื่อดูผลลัพธ์จากกระบวนงานพิมพ์ทั้งสาม อาจารย์ก็เดาได้ถูกต้องว่าเกิดอะไรขึ้น แต่แทนที่จะไปดูโค้ดโดยตรง เธอตัดสินใจลองสร้างโค้ดของ Anatoly กลับคืนจากการสังเกตผลลัพธ์เพียงอย่างเดียว เพื่อทำเช่นนั้น เธอตั้งสมมติฐานที่ถูกต้องดังนี้:

1. คำสั่งส่งออกในแต่ละกระบวนงานพิมพ์อยู่ในตำแหน่งที่ถูกต้อง (เช่น อยู่ระหว่างการเรียกแบบเรียกซ้ำสองครั้งในกระบวนงาน inPrint)

2. ในบรรดาการเรียกแบบเรียกซ้ำทั้งหกครั้งของกระบวนงานทั้งสาม มีการเรียก prePrint สองครั้งพอดี เรียก inPrint สองครั้งพอดี และเรียก postPrint สองครั้งพอดี แม้อาจอยู่ในกระบวนงานที่ผิดก็ตาม

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

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

ข้อมูลนำเข้ามีกรณีทดสอบเดียว ประกอบด้วยสตริงสามสตริงในสามบรรทัดแยกกัน ได้แก่ ผลลัพธ์ที่สังเกตได้จากกระบวนงาน prePrint, inPrint และ postPrint ของ Anatoly (ตามลำดับนี้) บนต้นไม้ทดสอบต้นหนึ่ง แต่ละสตริงประกอบด้วยตัวอักษรพิมพ์ใหญ่ $n$ ตัว ($4 \le n \le 26$) โดยไม่มีตัวอักษรซ้ำภายในสตริงใดเลย รับประกันว่ามีคำตอบอย่างน้อยหนึ่งแบบ

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

แสดงการสร้างกลับคืนที่เป็นไปได้ทั้งหมดสำหรับกรณีทดสอบ โดยเรียงตามคำอธิบายในย่อหน้าสุดท้ายด้านล่าง ผลลัพธ์ของแต่ละแบบมีสองส่วน ส่วนแรกมีหนึ่งบรรทัด อธิบายการเรียกทั้งหกในกระบวนงานของ Anatoly: เริ่มจากการเรียก (แบบเรียกซ้ำ) สองครั้งใน prePrint ตามด้วยการเรียกใน inPrint และสุดท้ายการเรียกใน postPrint ใช้คำ Pre, In และ Post แทนการเรียก โดยคั่นด้วยช่องว่าง ตัวอย่างเช่น หากกระบวนงานของ Anatoly ถูกต้อง ส่วนแรกของผลลัพธ์จะเป็น Pre Pre In In Post Post

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

การสร้างกลับคืนแต่ละแบบเป็นลำดับของโทเคน 6 ตัวที่เลือกจาก Pre, In และ Post เรียงการสร้างกลับคืนตามลำดับพจนานุกรม โดยใช้ลำดับโทเคนดังนี้: $\texttt{Pre} < \texttt{In} < \texttt{Post}$

ตัวอย่าง

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

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

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

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

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

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

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

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB