Xóa nút có một con (Delete a One-Child Node from a BST)

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 $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn; khóa trùng bị bỏ qua.

Cho khóa $x$ được bảo đảm tồn tại và nút mang khóa $x$ có đúng một nút con. Khi xóa $x$, nút con duy nhất của $x$ thay thế vị trí của $x$ trong cây:

• nếu $x$ không phải gốc, cha của $x$ được nối trực tiếp với nút con duy nhất đó;
• nếu $x$ là gốc, nút con duy nhất trở thành gốc mới.

Sau khi xóa, hãy in preorder của cây thu được.

Input

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

Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ theo thứ tự chèn.

Dòng thứ ba chứa khóa $x$ cần xóa.

Output

In các khóa của cây sau khi xóa theo preorder, cách nhau bởi một dấu cách.

Subtask

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

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

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

Trong tất cả các subtask, $a_i$ và $x$ là số nguyên có dấu 64-bit; khóa trùng bị bỏ qua khi dựng cây; $x$ tồn tại và nút mang khóa $x$ có đúng $1$ con.

Ví dụ

Input

4
8 3 10 14
10

Output

8 3 14

Giải thích

Sau khi dựng cây, nút $10$ là con phải của $8$ và chỉ có một con phải là $14$. Khi xóa $10$, nút $14$ được nối trực tiếp vào vị trí con phải của $8$.

Preorder của cây còn lại là 8 3 14.