Tinh tinh đào hoa (The Playboy Chimp)

Nguồn: UVa

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

Đề bài

Có $n$ con tinh tinh cái đứng thành một hàng theo chiều cao không giảm. Chiều cao lần lượt là:

Với mỗi chiều cao truy vấn $x$, cần tìm hai giá trị:

• chiều cao lớn nhất nhỏ hơn $x$;
• chiều cao nhỏ nhất lớn hơn $x$.

Những con có chiều cao đúng bằng $x$ không được chọn.

Nếu không tồn tại giá trị ở một phía, in chữ X cho phía đó.

Input

Dòng đầu chứa $n$.

Dòng thứ hai chứa $n$ chiều cao theo thứ tự không giảm.

Dòng thứ ba chứa $q$.

Dòng thứ tư chứa $q$ chiều cao truy vấn.

Output

Với mỗi truy vấn, in hai giá trị trên một dòng: giá trị thấp hơn gần nhất và giá trị cao hơn gần nhất. Dùng X nếu không tồn tại.

Subtask

• 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$.

Ví dụ

Input

4
1 4 5 7
4
4 6 8 10

Output

1 5
5 7
7 X
7 X

Giải thích

Dãy chiều cao là $[1,4,5,7]$.

• Với $x=4$, giá trị gần nhất phía dưới là $1$, phía trên là $5$.
• Với $x=6$, hai giá trị cần tìm là $5$ và $7$.
• Với $x=8$, giá trị thấp hơn gần nhất là $7$ và không có giá trị nào lớn hơn, nên in 7 X.
• Với $x=10$, kết quả cũng là 7 X.

Các giá trị đúng bằng $x$ luôn bị loại khỏi hai lựa chọn.