BST Search Path

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

A binary search tree (BST) is a binary tree in which, for every node with key $v$, every key in its left subtree is smaller than $v$ and every key in its right subtree is greater than $v$.

Initially the tree is empty. Insert $a_1,a_2,\ldots,a_n$ in the given order. To insert $a_i$, start at the root: go to the left child if $a_i$ is smaller than the current key, and to the right child if it is larger. Create a new node when the required child is empty. If the key already exists, ignore that insertion and leave the tree unchanged.

After the tree is built, search for the query key $x$. The search starts at the root and follows the same comparison rule. Print all keys of the visited nodes in order, from the root to the point where the search stops.

If a node with key $x$ is reached, the final status is FOUND. If the search reaches an empty branch without finding $x$, the final status is NOT FOUND.

Input

The first line contains an integer $n$ — the number of keys used to build the tree.

If $n>0$, the next line contains $n$ signed integers $a_1,a_2,\ldots,a_n$ in insertion order. If $n=0$, this line is absent.

The last line contains the query key $x$.

Output

If the tree is non-empty, print the visited keys separated by one space, followed by FOUND or NOT FOUND on the same line.

If the tree is empty, no node is visited; print only:

NOT FOUND

Subtasks

Subtask 1 (20 points): $0\le n\le 20$.

Subtask 2 (30 points): $0\le n\le 5000$.

Subtask 3 (50 points): $0\le n\le 200000$.

In all subtasks, $a_i$ and $x$ are signed 64-bit integers, so $-2^{63}\le a_i,x\le 2^{63}-1$. Duplicate insertion keys are ignored.

Examples

Input

7
8 3 10 1 6 14 4
6

Output

8 3 6 FOUND

Explanation

The first key $8$ becomes the root. To search for $x=6$, first visit $8$. Since $6<8$, move left to $3$. Since $6>3$, move right and reach $6$.

The visited keys are $8,3,6$, and the query key is found, so the final status is FOUND.