Xóa nút lá (Delete a Leaf 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$ là một nút lá, nghĩa là nút đó không có con trái và cũng không có con phải.

Hãy xóa nút mang khóa $x$ khỏi cây, sau đó in preorder của cây còn lại. Preorder thăm gốc trước, tiếp theo là cây con trái, rồi cây con phải.

Nếu $x$ là nút duy nhất của cây thì sau khi xóa, cây trở thành rỗng.

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

Nếu cây sau khi xóa còn nút, in dãy khóa theo preorder trên một dòng, các khóa cách nhau bởi một dấu cách.

Nếu cây trở thành rỗng, in EMPTY.

Subtask

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

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

Subtask 3 (50 điểm): $1\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 $0$ con.

Ví dụ

Input

7
8 3 10 1 6 14 4
4

Output

8 3 1 6 10 14

Giải thích

Trong BST được tạo ra, nút $4$ là con trái của nút $6$ và không có con nào, nên $4$ là một nút lá. Sau khi xóa nút $4$, các liên kết còn lại của cây không đổi.

Duyệt preorder cây mới cho dãy 8 3 1 6 10 14.