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 بمجرد ملاحظة المخرجات. ولهذا وضعت الافتراضات الصحيحة التالية:
تعليمة الإخراج في كل إجراء طباعة موجودة في الموضع الصحيح (مثلًا، بين الاستدعاءين العوديين في الإجراء
inPrint).من بين الاستدعاءات العودية الستة في الإجراءات الثلاثة، يوجد بالضبط استدعاءان إلى
prePrint، وبالضبط استدعاءان إلىinPrint، وبالضبط استدعاءان إلىpostPrint، وإن كانت قد تقع في الإجراءات الخطأ.
سرعان ما أدركت الأستاذة أن إعادة بناء شيفرة Anatoly وشجرة الاختبار من مخرجاته ليست مهمة بسيطة، وأن النتيجة قد لا تكون وحيدة. عليك مساعدتها في إيجاد كل عمليات إعادة البناء الممكنة لشيفرة Anatoly. إضافةً إلى ذلك، لكل عملية إعادة بناء، عليك إيجاد الشجرة الأولى أبجديًا (كما يوضح قسم الإخراج) التي تعطي المخرجات المرصودة.
الإدخال
يتكون الإدخال من حالة اختبار واحدة. تتكون الحالة من ثلاث سلاسل في ثلاثة أسطر منفصلة: المخرجات المرصودة لإجراءات Anatoly المسماة prePrint وinPrint وpostPrint (بهذا الترتيب) على شجرة اختبار ما. تتكون كل سلسلة من $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