CF1039A Timetable

有两个公交车站，分别记为 A 和 B，每天有 $n$ 辆公交车从 A 开往 B。从 A 到 B 的最短路径需要 $t$ 单位时间，但有些公交车可能会选择更长的路线。此外，公交车在途中允许相互超车。 在每个车站，都有一个按时间排序的公交车到达时刻列表。对于 A 站，这个列表为 $a_1 < a_2 < \ldots < a_n$，对于 B 站，这个列表为 $b_1 < b_2 < \ldots < b_n$。公交车总是按照时刻表从 A 出发并到达 B，但到达 B 的顺序可能与出发顺序不同。我们称某种到达顺序是“合法”的，如果每辆公交车到达 B 的时间至少比其离开 A 的时间晚 $t$ 单位时间。 已知对于每辆在 $a_i$ 时刻从 A 出发的公交车，其在 B 站最晚可能到达的时刻为 $b_{x_i}$，即在时刻表中的第 $x_i$ 个。换句话说，对于每个 $i$，存在一种合法的到达顺序，使得第 $i$ 辆出发的公交车到达 B 时排在第 $x_i$ 位（其他公交车的到达顺序可以任意），但不存在合法顺序使得第 $i$ 辆出发的公交车到达 B 时排在第 $x_i+1$ 位。 形式化地说，我们称排列 $p_1, p_2, \ldots, p_n$ 是合法的，如果对于所有 $i$ 都有 $b_{p_i} \ge a_i + t$。那么 $x_i$ 就是在所有合法排列中 $p_i$ 的最大值。 现在给定序列 $a_1, a_2, \ldots, a_n$ 和 $x_1, x_2, \ldots, x_n$，但未给出到达 B 站的时刻表。请你找出任意一个满足条件的 B 站时刻表 $b_1, b_2, \ldots, b_n$，或者判断不存在这样的时刻表。

输入的第一行包含两个整数 $n$ 和 $t$（$1 \leq n \leq 200\,000$，$1 \leq t \leq 10^{18}$），分别表示公交车数量和从 A 到 B 的最短行驶时间。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_1 < a_2 < \ldots < a_n \leq 10^{18}$），表示公交车从 A 站出发的时刻。 第三行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$1 \leq x_i \leq n$），其中第 $i$ 个数表示第 $i$ 辆公交车最晚可以在 B 站时刻表中的第 $x_i$ 个位置到达。

如果存在解，输出第一行 "Yes"（不带引号）。 第二行输出 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_1 < b_2 < \ldots < b_n \leq 3 \cdot 10^{18}$）。可以证明，如果存在解，则一定存在满足这些约束的解。如果有多组合法答案，可以输出任意一组。 如果不存在合法时刻表，输出一行 "No"（不带引号）。

以第一个样例和输出的时刻表 $b_1, b_2, \ldots, b_n$ 为例。 为了使 $x_1 = 2$，公交车可以按顺序 $(2, 1, 3)$ 到达。为了使 $x_2 = 2$ 和 $x_3 = 3$，公交车可以按顺序 $(1, 2, 3)$ 到达。$x_1$ 不能为 $3$，因为排列 $(3, 1, 2)$ 和 $(3, 2, 1)$（即第 $1$ 辆公交车到达第 $3$ 个）都不合法（有公交车到达得太早），$x_2$ 不能为 $3$，原因类似。 由 ChatGPT 4.1 翻译