The bright red buildings and skies of the University of Fireloo.

The University of Fireloo is about to build a new on-campus residence named University of Fireloo Place (UFP), a village with ~N~ apartment buildings!

Apparently, UFP's architects are quite superstitious, so they believe that the ~K~ distinct numbers ~u_1, \dots, u_K~ are "unlucky". As a result, for the ~i^\text{th}~ apartment building, they want the floors to be numbered from ~1~ to ~f_i~ inclusive, but removing all floors with unlucky floor numbers.

Now, the architects need your help to determine how many floors each apartment in UFP should really have.

Constraints

~1 \le N \le 1\,000\,000~
~1 \le K \le 500\,000~
~1 \le f_i \le 1\,000\,000~ ~(i = 1, \dots, N)~
~1 \le u_j \le 1\,000\,000~ ~(j = 1, \dots, K)~

For 20% of the points, ~N, f_i, u_j \le 100~, and ~K \le 10~ for all ~i~ and ~j~.

For an additional 30% of the points, ~N, f_i, u_j \le 100\,000~, and ~K \le 10\,000~ for all ~i~ and ~j~.

Input Specification

The first line contains ~K~, the number of unlucky numbers the architects have considered.

The second line contains distinct, space-separated positive integers ~u_1, \dots, u_K~, the unlucky numbers.

The third line contains ~N~, the number of apartments to be built in UFP.

For the next ~N~ lines, the ~i^\text{th}~ line contains ~f_i~, the top floor number of the ~i^\text{th}~ apartment. It is guaranteed that no top floor number is an unlucky number.

Output Specification

Output ~N~ lines, where the ~i^\text{th}~ line contains one integer denoting the actual number of floors the ~i^\text{th}~ apartment should have.

Sample Input

2
4 13
2
16
14

Sample Output

14
12