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_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$. 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. Examples ## Input InputThe 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 OutputFor each user, output one integer — the minimum influence $I(i, j)$ among all news items. ## Samples ```input1 1 3 1 5 3 2 1 4 2 2 4 1 3 3 2 ``` ```output1 2 0 ```$$