Ba kiểu duyệt và duyệt theo mức (Three DFS Traversals and Level Order)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Dựng BST từ dãy khóa $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn; khóa trùng bị bỏ qua.

Sau khi dựng cây, hãy in bốn thứ tự duyệt của cùng cây đó:

• preorder: gốc - trái - phải;
• inorder: trái - gốc - phải;
• postorder: trái - phải - gốc;
• level-order: thăm các nút theo từng mức từ trên xuống dưới; trong cùng một nút, con trái được đưa vào trước con phải.

Input

Dòng đầu chứa số nguyên $n$.

Nếu $n>0$, dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ theo thứ tự chèn. Nếu $n=0$, không có dòng chứa dãy khóa.

Output

In đúng bốn dòng theo thứ tự sau:

Dòng 1 là preorder.

Dòng 2 là inorder.

Dòng 3 là postorder.

Dòng 4 là level-order.

Trên mỗi dòng, các khóa cách nhau bởi một dấu cách. Nếu cây rỗng, cả bốn dòng đều là EMPTY.

Subtask

Subtask 1 (20 điểm): $0\le n\le 20$.

Subtask 2 (30 điểm): $0\le n\le 5000$.

Subtask 3 (50 điểm): $0\le n\le 200000$.

Trong tất cả các subtask, $-2^{63}\le a_i\le 2^{63}-1$. Khóa trùng bị bỏ qua khi dựng cây.

Ví dụ

Input

7
8 3 10 1 6 14 4

Output

8 3 1 6 4 10 14
1 3 4 6 8 10 14
1 4 6 3 14 10 8
8 3 10 1 6 14 4

Giải thích

Khóa $8$ là gốc; $3$ và $10$ là hai con của gốc. Từ cùng cấu trúc cây, preorder thăm gốc trước, inorder thăm gốc giữa hai cây con, postorder thăm gốc sau cùng, còn level-order đi lần lượt theo từng mức.

Vì vậy bốn dòng output lần lượt là bốn thứ tự duyệt được yêu cầu.