Đường tìm kiếm trong BST (BST Search Path)

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

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

Đề bài

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là cây nhị phân trong đó, với mỗi nút có khóa $v$, mọi khóa trong cây con trái đều nhỏ hơn $v$ và mọi khóa trong cây con phải đều lớn hơn $v$.

Ban đầu cây rỗng. Các khóa $a_1,a_2,\ldots,a_n$ được chèn lần lượt theo đúng thứ tự đã cho. Khi chèn một khóa $a_i$, bắt đầu từ gốc: nếu $a_i$ nhỏ hơn khóa tại nút hiện tại thì đi sang con trái; nếu lớn hơn thì đi sang con phải. Khi gặp vị trí con rỗng, tạo nút mới tại vị trí đó. Nếu khóa đã tồn tại trong cây thì lần chèn đó bị bỏ qua và cấu trúc cây không thay đổi.

Sau khi dựng cây, cần tìm khóa truy vấn $x$. Quá trình tìm kiếm cũng bắt đầu từ gốc và dùng cùng quy tắc so sánh. Hãy in toàn bộ các khóa của những nút được thăm, theo đúng thứ tự từ gốc đến vị trí quá trình tìm kiếm kết thúc.

Nếu gặp nút có khóa bằng $x$, trạng thái cuối là FOUND. Nếu đi đến một nhánh rỗng mà chưa gặp $x$, trạng thái cuối là NOT FOUND.

Input

Dòng đầu chứa số nguyên $n$ — số khóa được đưa vào quá trình dựng cây.

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$, dòng này không xuất hiện.

Dòng cuối chứa số nguyên $x$ — khóa cần tìm.

Output

Nếu cây không rỗng, in trên một dòng các khóa của những nút được thăm, cách nhau bởi một dấu cách, sau đó in trạng thái FOUND hoặc NOT FOUND.

Nếu cây rỗng, không có nút nào được thăm; khi đó chỉ in:

NOT FOUND

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, $a_i$ và $x$ là số nguyên có dấu 64-bit, tức $-2^{63}\le a_i,x\le 2^{63}-1$. Khóa trùng trong dãy chèn bị bỏ qua.

Ví dụ

Input

7
8 3 10 1 6 14 4
6

Output

8 3 6 FOUND

Giải thích

Khóa đầu tiên $8$ trở thành gốc. Khi tìm $x=6$, trước hết thăm nút $8$. Vì $6<8$, chuyển sang cây con trái và thăm nút $3$. Vì $6>3$, chuyển sang cây con phải và gặp nút $6$.

Các nút được thăm lần lượt là $8,3,6$ và khóa cần tìm đã xuất hiện, nên trạng thái cuối là FOUND.