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. נוסף על כך, לכל שחזור עליכם למצוא את העץ הראשון בסדר אלפביתי (כמתואר בחלק הפלט) שנותן את הפלט שנצפה.
קלט
הקלט מורכב ממקרה בדיקה יחיד. הוא מכיל שלוש מחרוזות בשלוש שורות נפרדות: הפלט שנצפה מהפרוצדורות 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