4293. [TIOJ - 114學年度複試] Communication

【题目背景】

pooh 很想买 Ina 的五周年纪念商品，因此他决定要去打工。他打的工是要帮忙 TOI 办团康活动，TOI 选训营中很常会玩 Gartic Phone，这是一个充满沟通（Communication）的活动。

【题目描述】

选训营里面有 $N$ 个人要玩 Gartic Phone，编号为 $1, 2, \dots, N$。每个人都有一个作答时间 $w$，编号 $i$ 的人作答时间为 $w_i$。假设一场 Gartic Phone 有 $k$ 人参加，依序为 $p_1, p_2, \dots, p_k$，那么依序会由 $p_1$ 画给 $p_2$ 猜，$p_2$ 画给 $p_3$ 猜，到最后 $p_{k-1}$ 画给 $p_k$ 猜。我们称这样的一场 Gartic Phone 为 $(p_1, p_2, \dots, p_k)$，从 $p_1$ 开始，$p_k$ 结束，花的时间是 $\sum_{i=1}^k w_{p_i}$。

众所周知，选训营里面很多人都喜欢讲怪话或画怪画，因此 pooh 先预先收集了每个人的怪画度 $a$ 与怪话度 $b$，编号为 $i$ 的人的怪画度为 $a_i$，怪话度为 $b_i$。pooh 发现 Gartic Phone 要好玩有两个重要的参数：

怪度下限 $L$ 与怪度上限 $R$。

当 $u$ 要画给 $v$ 猜时，如果 $a_u + b_v < L$ 的话就会因为太不怪而变得很无聊，$a_u + b_v > R$ 的话又会因为太怪而让游戏进行不下去。

因此 pooh 只允许满足 $L \le a_u + b_v \le R$ 的 $u$ 画给 $v$ 猜。

注意在 $k=1$ 时，$(p_1)$ 一定是一个 pooh 允许的 Gartic Phone。

喂喂（编号 1 的人）想知道对于所有可能的结束人选 $i = 1, 2, \dots, N$：所有 1 开始，$i$ 结束的 pooh 允许的 Gartic Phone 中，花的时间最少是多少？

【输入格式】

第一行会有三个正整数 $N, L, R$，代表有几个人要玩 Gartic Phone 与怪度下限、怪度上限分别是多少。

第二行有 $N$ 个正整数 $a_1, a_2, \dots, a_N$，代表这 $N$ 个人的怪画度。

第三行有 $N$ 个正整数 $b_1, b_2, \dots, b_N$，代表这 $N$ 个人的怪话度。

第四行有 $N$ 个正整数 $w_1, w_2, \dots, w_N$，代表这 $N$ 个人的作答时间。

【输出格式】

输出一行，$N$ 个整数 $d_1, d_2, \dots, d_N$。

当不存在 1 开始，$i$ 结束的路线时，$d_i = -1$。否则 $d_i$ 为最短时间。

【样例输入】

5 3 7
1 2 3 4 5
2 4 1 1 5
4 1 7 2 8

【样例输出】

4 5 12 7 12

【样例说明】

对于样例一，每个结束的人最快结束的组合如下：(1), (1, 2), (1, 2, 3), (1, 2, 4), (1, 5)。

【数据规模与约定】

• $1 \le N \le 5 \times 10^5$
• $1 \le a_i, b_i \le 5 \times 10^8$
• $1 \le L \le R \le 10^9$
• $1 \le w_i \le 10^9$
• 大洋里（仅提供子任务 $4$ 与子任务 $6$ 各一个）
  

【来源】

114 学年度台湾省建国中学信息学科能力竞赛：复试