Anatoly Cheng McDougal là một sinh viên điển hình về nhiều mặt. Bất cứ khi nào có thể, cậu đều cố cắt dán mã thay vì viết từ đầu. Cách làm này tất yếu gây ra rắc rối. Chẳng hạn, khi mới học các phép duyệt cây tiền thứ tự, trung thứ tự và hậu thứ tự và được cho mã in cây theo tiền thứ tự (ở bên trái phía dưới), cậu chỉ cắt dán mã, chuyển lệnh in tới vị trí đúng rồi đổi tên thủ tục. Tuy nhiên, cậu quên đổi tên các lời gọi thủ tục bên trong mã, tạo ra mã in trung thứ tự và hậu thứ tự bị lỗi như dưới đây.

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);
}

Đến đây, Anatoly lại không hành xử như một sinh viên điển hình: cậu thực sự đã kiểm thử mã! Tiếc rằng khi kết quả không đúng, cậu lại trở về hành vi quen thuộc của sinh viên. Cậu hoảng hốt và bắt đầu thay đổi ngẫu nhiên các lời gọi trong cả ba thủ tục, hy vọng sẽ sửa được. Không cần nói cũng biết, tình hình còn tệ hơn lúc đầu.

Giáo sư của Anatoly kiểm thử mã trên một cây ký tự ngẫu nhiên. Nhìn kết quả của ba thủ tục in, cô đoán đúng điều đã xảy ra. Tuy nhiên, thay vì xem thẳng mã, cô quyết định thử khôi phục mã của Anatoly chỉ bằng cách quan sát kết quả. Để làm vậy, cô đưa ra các giả định đúng sau:

1. Lệnh xuất trong mỗi thủ tục in nằm đúng vị trí (ví dụ, nằm giữa hai lời gọi đệ quy trong thủ tục inPrint).

2. Trong sáu lời gọi đệ quy của ba thủ tục, có đúng hai lời gọi tới prePrint, đúng hai tới inPrint và đúng hai tới postPrint, dù chúng có thể nằm trong các thủ tục không đúng.

Giáo sư sớm nhận ra rằng khôi phục mã của Anatoly và cây kiểm thử từ kết quả không đơn giản, và kết quả khôi phục có thể không duy nhất. Bạn phải giúp cô tìm tất cả các cách khôi phục mã của Anatoly. Ngoài ra, với mỗi cách, bạn cần tìm cây đứng đầu theo thứ tự chữ cái (được mô tả trong phần dữ liệu ra) tạo ra kết quả đã quan sát.

Dữ liệu vào

Dữ liệu vào gồm một bộ kiểm thử. Bộ kiểm thử gồm ba xâu trên ba dòng riêng biệt: kết quả quan sát được của các thủ tục prePrint, inPrint và postPrint của Anatoly (theo thứ tự đó) trên một cây kiểm thử nào đó. Mỗi xâu gồm $n$ chữ cái in hoa ($4 \le n \le 26$), không có chữ cái lặp lại trong bất kỳ xâu nào. Đảm bảo có ít nhất một lời giải.

Dữ liệu ra

In tất cả các cách khôi phục có thể của bộ kiểm thử, theo thứ tự mô tả ở đoạn cuối bên dưới. Dữ liệu ra cho mỗi cách khôi phục gồm hai phần. Phần đầu tiên là một dòng mô tả sáu lời gọi trong các thủ tục của Anatoly: trước tiên là hai lời gọi (đệ quy) trong prePrint, tiếp theo là các lời gọi trong inPrint, và cuối cùng là các lời gọi trong postPrint. Các lời gọi được biểu diễn bằng các từ Pre, In và Post, cách nhau bởi dấu cách. Ví dụ, nếu các thủ tục của Anatoly đúng, phần đầu tiên của cách khôi phục sẽ là Pre Pre In In Post Post.

Phần thứ hai gồm ba dòng, mô tả cây kiểm thử đầu tiên có thể tạo ra các kết quả quan sát được. Dòng đầu là kết quả in tiền thứ tự đúng của cây, dòng thứ hai và thứ ba lần lượt là kết quả in trung thứ tự và hậu thứ tự đúng. Cây đầu tiên là cây có kết quả in tiền thứ tự đứng đầu theo thứ tự chữ cái. Nếu có nhiều cây như vậy, chọn cây có kết quả in trung thứ tự đứng đầu theo thứ tự chữ cái trong số đó.

Mỗi cách khôi phục là một dãy 6 ký hiệu được chọn từ Pre, In và Post. Các cách khôi phục được sắp xếp theo thứ tự từ điển với thứ tự ký hiệu như sau: $\texttt{Pre} < \texttt{In} < \texttt{Post}$.

Ví dụ

Dữ liệu vào 1

HFBIGEDCJA
BIGEDCJFAH
BIGEDCJFAH

Dữ liệu ra 1

Pre Post In Post In Pre
HFBJCDEGIA
BIGEDCJFAH
IGEDCJBAFH

Dữ liệu vào 2

BNLFAGHPEDOCMJIK
NLBGAPHCODEIJMKF
NLFAGHPEDOCMJIKB

Dữ liệu ra 2

In Pre In Post Post Pre
BLNFKMEHAGPCODIJ
NLBAGHPEODCMIJKF
NLGAPHDOCEJIMKFB

Post Pre In In Post Pre
BLNFKICPGAHEODMJ
NLBGAPHCODEIJMKF
NLAGHPDOECJMIKFB