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