Chess Team Forming

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of members in the Polycarp's team.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ is the skill value of the $$$i$$$-th player of the Polycarp's team.

The third line contains $$$n+1$$$ integers $$$b_1, b_2, \dots, b_{n+1}$$$ ($$$1 \le b_j \le 10^9$$$), where $$$b_j$$$ is the skill value of the $$$j$$$-th player of the opposing team.

The fourth line contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of options for the final player.

The fifth line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_k \le 10^9$$$), where $$$c_k$$$ is the skill value of the $$$k$$$-th of the options for the final player of the Polycarp's team.

Output:

Print $$$m$$$ integers — the $$$k$$$-th of them should be equal to the smallest difficulty of the game for the team Polycarp can achieve if he picks the $$$k$$$-th option player as the final one.

Sample Input:

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

Sample Output:

4 2 3 4 2

Sample Input:

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

Sample Output:

3 3 3 3 3 2 2 2 1 0

Sample Input:

1
10
10 5
2
5 15

Sample Output:

0 -5

Note:

In the first example the optimal pairings for the first three options are the following. Note that there might be multiple valid pairing for the minimum answer.

First option:

Polycarp's team: 6 1 3 1 10 4

Opposing team:  9 4 2 5  9 8

The respective difficulties of the game for each player are: 3, 3, -1, 4, -1, 4. The maximum is 4, thus it's the difficulty of the game for the team.

Second option:

Polycarp's team: 10 4 1 3 7 6

Opposing team:   9 4 2 5 9 8

Third option:

Polycarp's team: 6 3 1 4 10 6

Opposing team:  9 4 2 5  9 8