假设您是新闻网站的所有者,想要研究某些选定的新闻项目如何影响您的用户。
你有 $$$n$$$ 条新闻,对于每条新闻,你已经确定了两个参数:它涉及政治 $$$p_i$$$ 的程度以及涉及文化 $$$c_i$$$ 的程度。
您还有 $$$m$$$ 用户对您想要研究的新闻的反应。对于每个人,你已经确定了三个参数:对政治新闻的容忍度$$$tp_j$$$,对文化新闻的容忍度$$$tc_j$$$,以及“影响范围”$$$d_j$$$。
新闻$$$i$$$中的政治$$$I_p(i, j)$$$和文化$$$I_c(i, j)$$$对用户$$$j$$$的影响可以通过以下公式计算:
换句话说,虽然政治量$$$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)$$$。
输入
第一行包含一个整数 $$$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)$$$。
示例
输入复制
62 4 1 6 0 103 2 6 1 9 050 0 0 1 50 0 9 5 29 4 8 2 2
输出复制
5 4 1 2 2
输入复制
575 19 53 12 1034 75 67 84 95555 14 46 97 1478 61 56 23 3310 4 7 11 3
输出复制
0 18 53 34 36