The Playboy Chimp

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

You are given $n$ heights in non-decreasing order. For each query height $x$, find:

• the greatest height strictly smaller than $x$;
• the smallest height strictly greater than $x$.

Heights equal to $x$ must not be selected. Print X whenever one side does not exist.

Input

The first line contains $n$.

The second line contains the $n$ heights in non-decreasing order.

The third line contains $q$.

The fourth line contains the $q$ query heights.

Output

For each query, print the nearest strictly smaller height and the nearest strictly greater height. Use X if one of them does not exist.

Subtasks

• Subtask 1 — 20%: $1\le n,q\le100$.
• Subtask 2 — 30%: $1\le n\le5000$, $1\le q\le5000$.
• Subtask 3 — 50%: $1\le n\le50000$, $1\le q\le25000$, $1\le h_i,x\le2^{31}-1$.

Examples

Input

4
1 4 5 7
4
4 6 8 10

Output

1 5
5 7
7 X
7 X

Explanation

For $x=4$, the greatest height below $4$ is $1$, and the smallest height above $4$ is $5$. A height equal to $4$ is excluded.