【题目描述】

科技节的接力项目需要两名队员共同完成．每名队员在负责接棒和负责交棒时的耗时不同，教练希望评估每名队员与所有其他队员合作时的总耗时．

共有 $n$ 名队员，第 $i$ 名队员有两个非负整数参数 $x_i,y_i$．

当队员 $i$ 与队员 $j$ 合作时，可以采用以下两种分工之一：

• 队员 $i$ 负责第一阶段，队员 $j$ 负责第二阶段，耗时为 $x_i+y_j$；
• 队员 $j$ 负责第一阶段，队员 $i$ 负责第二阶段，耗时为 $x_j+y_i$．

两名队员总会选择耗时较少的分工方式，因此队员 $i$ 与队员 $j$ 的合作耗时为

$$c(i,j)=\min(x_i+y_j,x_j+y_i).$$

对于每名队员 $i$，请计算他分别与其他 $n-1$ 名队员合作一次的总耗时，即

$$ans_i=\sum_{\substack{1\le j\le n\\j\ne i}}c(i,j).$$

【输入描述】

第一行输入一个整数 $n$，表示队员数量．

第二行输入 $n$ 个整数 $x_1,x_2,\ldots,x_n$，表示每名队员负责第一阶段时的耗时参数．

第三行输入 $n$ 个整数 $y_1,y_2,\ldots,y_n$，表示每名队员负责第二阶段时的耗时参数．

【输出描述】

输出一行 $n$ 个整数 $ans_1,ans_2,\ldots,ans_n$，其中 $ans_i$ 表示第 $i$ 名队员与所有其他队员合作的总耗时．

【样例 1】

【样例 1 输入】

4
1 5 2 4
4 1 3 2

【样例 1 输出】

9 10 11 12

【样例 1 解释】

六对队员之间的合作耗时分别为

$$c(1,2)=2,\quad c(1,3)=4,\quad c(1,4)=3,$$ $$c(2,3)=3,\quad c(2,4)=5,\quad c(3,4)=4.$$

例如，第 $1$ 名队员的答案为 $2+4+3=9$．

【样例 2】

【样例 2 输入】

3
0 0 0
7 2 5

【样例 2 输出】

7 4 7

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans．

该样例满足子任务 $1$ 的范围 $n\le 2000$．

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．

该样例满足子任务 $2$ 的特殊性质：所有 $y_i=0$．

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．

该样例满足子任务 $3$ 的特殊性质：$x_1-y_1\le x_2-y_2\le\cdots\le x_n-y_n$．

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．

该样例对应子任务 $4$，不具有子任务 $1\sim3$ 的范围或特殊性质．

【数据规模与约定】

对于所有测试数据，保证：

• $2\le n\le5\times10^5$；
• $0\le x_i,y_i\le10^9$．

答案可能超过 $32$ 位有符号整数的表示范围．

子任务编号	分数	特殊性质
$1$	$30$	$n\le2000$
$2$	$15$	$y_i=0$
$3$	$25$	$x_1-y_1\le x_2-y_2\le\cdots\le x_n-y_n$
$4$	$30$	无特殊性质

各子任务独立计分．只有通过一个子任务中的全部测试点，才能获得该子任务的分数．

【大样例下载链接】

点击下载本题选手目录