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

假设你是某新闻网站的所有者，希望研究若干选定的新闻条目对用户的影响。

你共有 $n$ 条新闻，对每条新闻 $i$，你已预先确定两个参数：其政治相关度 $p_i$ 和文化相关度 $c_i$。

你还拥有 $m$ 名用户，希望研究他们对这些新闻的反应。对每位用户 $j$，你已预先确定三个参数：其对政治类新闻的容忍度 $tp_j$、对文化类新闻的容忍度 $tc_j$，以及“影响区间” $d_j$。

新闻条目 $i$ 对用户 $j$ 在政治方面的影响 $I_p(i, j)$ 和在文化方面的影响 $I_c(i, j)$ 可由以下公式计算：

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

换言之，当政治相关度 $p_i$ 小于容忍度 $tp_j$ 时，该新闻不会对用户产生影响；否则，该主题开始令用户感到不适，但其影响上限为 $tp_j + d_j$。文化相关度同理。

新闻条目 $i$ 对用户 $j$ 的总影响定义为 $I(i, j) = I_p(i, j) + I_c(i, j)$。

对每位用户 $j$，请找出其受所有新闻条目 $i$ 影响的最小总影响值 $I(i, j)$。

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.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 新闻条目的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$0 \le p_i \le 10^6$）—— 每条新闻的政治内容量。

第三行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$0 \le c_i \le 10^6$）—— 每条新闻的文化内容量。

第四行包含一个整数 $m$（$1 \le m \le 4 \cdot 10^5$）—— 用户的数量。

第五行包含 $m$ 个整数 $tp_1, tp_2, \dots, tp_m$（$0 \le tp_j \le 10^6$）—— 每个用户的政治理解度。

第六行包含 $m$ 个整数 $tc_1, tc_2, \dots, tc_m$（$0 \le tc_j \le 10^6$）—— 每个用户的文化理解度。

第七行包含 $m$ 个整数 $d_1, d_2, \dots, d_m$（$0 \le d_j \le 10^6$）—— 每个用户的影响力范围。

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

对每个用户，输出一个整数——所有新闻项中最小的影响值 $I(i, j)$。

null