TLE '17 Contest 2 P2 - Unlucky Numbers

View as PDF

Submit solution

Points: 5
Time limit: 3.0s
Memory limit: 256M

Problem type
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^{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 \leq N \leq 1\,000\,000
1 \leq K \leq 500\,000
1 \leq f_i \leq 1\,000\,000 (i = 1, \dots, N)
1 \leq u_j \leq 1\,000\,000 (j = 1, \dots, K)

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

For an additional 30% of the points, N, f_i, u_j \leq 100\,000, and K \leq 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^{th} line contains f_i, the top floor number of the i^{th} apartment. It is guaranteed that no top floor number is an unlucky number.

Output Specification

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

Sample Input

2
4 13
2
16
14

Sample Output

14
12

Comments

There are no comments at the moment.