E. 最小影响 / Minimum Influence

题目描述

假设你是一家新闻网站的所有者，想要研究一些精选新闻如何影响用户。

你有 $n$ 条新闻，每条新闻已确定两个参数：政治内容量 $p_i$ 和文化内容量 $c_i$。

你还有 $m$ 位用户，每位用户已确定三个参数：政治容忍度 $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 < tp_j \\ p_i & \text{if } tp_j \le p_i < 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 < tc_j \\ c_i & \text{if } tc_j \le c_i < 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, j)$ 值。

输入格式

第一行包含一个整数 $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$) — 每位用户的影响区间。

输出格式

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

样例

1
3
1 5 3
2 1 4
2
2 4
1 3
3 2

2
0