Statement : E. Minimum Influence

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$.

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 \\ tp_j + d & \text{if } p_i \ge tp_j + d \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 \\ tc_j + d & \text{if } c_i \ge tc_j + d \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$. 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$$$.

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.

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

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