Broadcast Frequency Bracket Finder

A community radio cooperative has already assigned n distinct broadcast frequencies to its transmitter towers. Whenever a listener requests a frequency to tune to, the cooperative reports two bracket frequencies chosen from among the ones already assigned: the largest assigned frequency that does not exceed the request, and the smallest assigned frequency that is not smaller than the request. Either bracket may fail to exist, in which case it is reported as -1.

Given the n assigned frequencies and q listener requests, compute both brackets for every request.

Input format

• Line 1: a single integer n.
• Line 2: n distinct integers, the assigned frequencies (given in no particular order).
• Line 3: a single integer q.
• Line 4: q integers, the requested frequencies, in the order they should be answered.

Output format

Print q lines. On the i-th line print two integers separated by a single space: the floor bracket (the largest assigned frequency <= the i-th request, or -1 if none) followed by the ceiling bracket (the smallest assigned frequency >= the i-th request, or -1 if none).

Constraints

• 1 <= n <= 200000
• 1 <= q <= 200000
• 0 <= frequency <= 10^9 for both assigned frequencies and requests.
• All n assigned frequencies are pairwise distinct.
• Requested frequencies may repeat and may coincide with an assigned frequency.

5
90 101 200 350 500
3
100 200 501

90 101
200 200
500 -1

1
500
3
500 100 999

500 500
-1 500
500 -1