Multiple Predecessor and Successor Queries

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from $a_1,a_2,\ldots,a_n$ in insertion order. If a key appears more than once, only its first occurrence creates a node; later duplicates are ignored.

For each query value $x$, which does not have to exist in the tree, determine two strict neighboring keys by value:

• the predecessor is the largest stored key $p$ such that $p<x$;
• the successor is the smallest stored key $s$ such that $s>x$.

If one side has no qualifying key, its result is NONE.

Input

The first line contains $n$.

If $n>0$, the next line contains $n$ keys $a_1,a_2,\ldots,a_n$. If $n=0$, this line is absent.

The next line contains $q$ — the number of queries.

Each of the next $q$ lines contains one integer $x$.

Output

For each query, print one line in the exact order predecessor successor.

Print NONE in the first field if the predecessor does not exist, and NONE in the second field if the successor does not exist.

Subtasks

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

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

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

In all subtasks, every stored key and query value is a signed 64-bit integer.

Examples

Input

7
8 3 10 1 6 14 4
3
6
1
9

Output

4 8
NONE 3
8 10

Explanation

For $x=6$, the largest key below $6$ is $4$ and the smallest key above $6$ is $8$.

For $x=1$, no key is smaller than $1$, while the successor is $3$, so the result is NONE 3.

For $x=9$, the predecessor is $8$ and the successor is $10$.