P12929 [POI 2022/2023 R2] 攀登 / Wspinaczka

翻译来自于 [LibreOJ](https://loj.ac/p/5024)。

**题目译自 [XXX Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi30-2/dashboard/) [Wspinaczka](https://szkopul.edu.pl/problemset/problem/dqDbPTjXtS9KK9xXHD4qAiie/statement/)** Bajtocka 山是 Bajtocja 的最高峰，沿途有一条风景如画的登山步道。步道上有 $n$ 个位于不同高度的林间空地，第 $i$ 个空地位于 $i$ 米高度。$m$ 条登山路径（有时为绕过某些空地的栈桥）连接这些空地，每条路径通向上方。每块空地有其摄影吸引力，用整数表示。 为确保安全，禁止离开指定路径！此地天气瞬息万变，常有暴雨侵袭，游客只能在空地的专用凉亭避雨。因此，每条路径连接的空地高度差不超过 $k$ 米。 Bajtocka 摄影协会（BKF）的 $n$ 名摄影师计划登上 Bajtocka 山。他们将一起攀登至某空地 $p$，然后分散行动。每人仅沿登山路径向上移动，拍摄途经空地的照片（因技术限制，仅能在空地拍摄，无法在路径上拍出好照片）。每人可选择任意空地结束行程。 最后，摄影师们会计算探险的风景值——所有拍摄空地的摄影吸引力之和（每块空地最多贡献一张照片的吸引力值）。 BKF 尚未决定从哪块空地 $p$ 开始并分散。请帮助他们，为每种可能的 $p$ 选择计算从该空地开始探险的最大风景值。

第一行包含三个整数 $n, m, k$ $(2 \leq n \leq 100000, 1 \leq m \leq 800000, 1 \leq k \leq 8)$，分别表示空地数、路径数和路径最大高度差。 第二行包含 $n$ 个整数 $f_1, \ldots, f_n$ $(1 \leq f_i \leq 10^9)$，表示各空地的摄影吸引力。 接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ $(1 \leq a_i < b_i \leq n, b_i \leq a_i + k)$，表示从空地 $a_i$ 到 $b_i$ 的路径。路径互不相同。

输出 $n$ 行，第 $i$ 行包含一个整数，表示从空地 $p=i$ 开始并分散的最大风景值。

**附加样例** 1. $n=5, m=4, k=1$，$f_i = 2^{i-1}$。 2. $n=30, k=2$，$f_i = 998244353 - 2^{i-1}$，每块空地有路径到后两块空地（若存在）。 3. $n=1000, k=8$，$f_i = i$，每块空地有路径到编号不互质的空地。 4. $n=100000, k=8$，$f_i = 1$，空地间有路径当十进制表示有公共数字。 5. $n=100000, k=8$，每块空地有路径到距离为偶数的空地。 所有测试数据均满足路径仅连接高度差不超过 $k$ 米的空地。 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | 除最后空地外，每块空地向上有恰一条路径 | $10$ | | $2$ | $n \leq 1000$ | $10$ | | $3$ | $f_i = 1$ 对每个 $i$ | $20$ | | $4$ | $k \leq 2$ | $15$ | | $5$ | 无附加限制 | $45$ |