Floor and ceiling of a price

Problem

Rahul works part-time at a mobile shop in Chennai. The shop keeps phone prices in a binary search tree, inserted in the given order into an empty tree.

Customers come with a budget x. For each budget, print the floor: the highest price that is at most x. Also print the ceiling: the lowest price that is at least x. Print NONE when no such price exists.

Input, output and limits

Input: Line 1: n. Line 2: n different prices, in insertion order. Line 3: q. Line 4: the q budgets.
Output: q lines. Each line has the floor and the ceiling, separated by a space. Each one is a price or NONE.
Constraints: 1 ≤ n ≤ 1000
1 ≤ q ≤ 1000
1 ≤ every price, every budget ≤ 10^9
The n prices are all different.

Examples

Example

Input

5
50 30 70 20 40
4
45 40 10 90

Output

40 50
40 40
NONE 20
70 NONE

For 45 the floor is 40 and the ceiling 50. 40 is a price, so it is both. Nothing is at most 10, and nothing is at least 90.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Walk down from the root as in a search. A node with a price at most x could be the floor, and a node with a price at least x could be the ceiling.

Hint 2

When a node is at most x, remember it and go right to look for a closer one. When it is larger, go left.

Hint 3

If you meet a node equal to x, it is both the floor and the ceiling.

Hint 4

Find the floor and the ceiling with two separate walks to keep the code simple.

Write your Java code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More BST problems

Problem

Input, output and limits

Examples

Hints

More BST problems