E. Minimum Influence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Imagine that you are the owner of a news website and want to study how some selected news items affect your users.

You have $$$n$$$ news items, and for each of them, you have already determined two parameters: how much it touches politics $$$p_i$$$ and how much it touches culture $$$c_i$$$.

You also have $$$m$$$ users whose reaction to the news you want to study. For each person, you have already determined three parameters: tolerance to political news $$$tp_j$$$, tolerance to cultural news $$$tc_j$$$, and the "zone of influence" $$$d_j$$$.

The influence of politics $$$I_p(i, j)$$$ and culture $$$I_c(i, j)$$$ in news item $$$i$$$ on user $$$j$$$ can be calculated by the following formulas:

$$$$$$ \begin{array}{ c c } I_p(i, j) = \begin{cases} 0 & \text{if } p_i \lt tp_j \\ p_i & \text{if } tp_j \le p_i \lt tp_j + d_j \\ tp_j + d_j & \text{if } p_i \ge tp_j + d_j \end{cases}, & I_c(i, j) = \begin{cases} 0 & \text{if } c_i \lt tc_j \\ c_i & \text{if } tc_j \le c_i \lt tc_j + d_j \\ tc_j + d_j & \text{if } c_i \ge tc_j + d_j \end{cases} \end{array}. $$$$$$

In other words, while the amount of politics $$$p_i$$$ is less than the tolerance level $$$tp_j$$$, it does not affect the user. Otherwise, the topic starts to irritate the user, but not more than up to $$$tp_j + d_j$$$. The same goes for culture.

The total influence of news item $$$i$$$ on user $$$j$$$ is $$$I(i, j) = I_p(i, j) + I_c(i, j)$$$.

For each user $$$j$$$, determine the minimum influence $$$I(i, j)$$$ among all news items $$$i$$$.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of news items.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le 10^6$$$) — the amount of political content of each news item.

The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$0 \le c_i \le 10^6$$$) — the amount of cultural content of each news item.

The fourth line contains one integer $$$m$$$ ($$$1 \le m \le 4 \cdot 10^5$$$) — the number of users.

The fifth line contains $$$m$$$ integers $$$tp_1, tp_2, \dots, tp_m$$$ ($$$0 \le tp_j \le 10^6$$$) — the political tolerance of each user.

The sixth line contains $$$m$$$ integers $$$tc_1, tc_2, \dots, tc_m$$$ ($$$0 \le tc_j \le 10^6$$$) — the cultural tolerance of each user.

The seventh line contains $$$m$$$ integers $$$d_1, d_2, \dots, d_m$$$ ($$$0 \le d_j \le 10^6$$$) — the zone of influence of each user.

Output

For each user, output one integer — the minimum influence $$$I(i, j)$$$ among all news items.

Examples
Input
6
2 4 1 6 0 10
3 2 6 1 9 0
5
0 0 0 1 5
0 0 9 5 2
9 4 8 2 2
Output
5
4
1
2
2
Input
5
75 19 53 12 10
34 75 67 84 95
5
55 14 46 97 14
78 61 56 23 33
10 4 7 11 3
Output
0
18
53
34
36