Ở một vương quốc nọ, nhà vua muốn đầu tư cơ sở hạ tầng cho ~q~ ngôi làng.

Có tất cả ~n~ công trình với các mức chi phí khác nhau, công trình thứ ~i~ có chi phí là ~a_i~. Các công trình có chi phí cao hơn sẽ mang lại nhiều lợi ích hơn cho ngôi làng. Tuy nhiên, mỗi ngôi làng chỉ có thể chọn công trình có chi phí không vượt quá số vốn ~x~ của mình.

Với mỗi làng, hãy tìm công trình có chi phí cao nhất mà làng đó có thể đầu tư. Nếu không có công trình nào phù hợp, trả về ~-1~.

Input

• Dòng đầu gồm số nguyên ~n~ là số lượng công trình ~(1 \leq n \leq 10^5)~.
• Dòng thứ hai gồm ~n~ số là chi phí của các công trình ~a_1, a_2,\dots, a_n~ ~(1 \leq a_i \leq 10^5)~.
• Dòng thứ ba gồm số nguyên ~q~ là số lượng ngôi làng ~(1 \leq q \leq 10^5)~.
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo mỗi dòng gồm ~x_i~ là số vốn của làng thứ ~i~ ~(1 \leq x_i \leq 10^5)~.

Output

Gồm ~q~ dòng, mỗi dòng là chi phí của công trình phù hợp nhất cho làng, hoặc ~-1~ nếu không có công trình nào phù hợp.

Ràng buộc

• ~50\%~ số test ứng với ~50\%~ số điểm có ~n \times q \leq 10^6~
• ~50\%~ số test còn lại không có ràng buộc gì thêm

Sample Test

Input

5
2 4 6 8 10
6
1
3
5
7
9
11

Output

-1
2
4
6
8
10