题目描述

题目译自 XXX Olimpiada Informatyczna – II etap Wspinaczka

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$ 开始并分散的最大风景值。

样例

输入

4 4 2
3 4 5 1
1 2
2 4
1 3
3 4

输出

13
5
6
1

附加样例

• $n=5$, $m=4$, $k=1$，$f_i = 2^{i-1}$。
• $n=30$, $k=2$，$f_i = 998244353 - 2^{i-1}$，每块空地有路径到后两块空地（若存在）。
• $n=1000$, $k=8$，$f_i = i$，每块空地有路径到编号不互质的空地。
• $n=100000$, $k=8$，$f_i = 1$，空地间有路径当十进制表示有公共数字。
• $n=100000$, $k=8$，每块空地有路径到距离为偶数的空地。

数据范围与提示

所有测试数据均满足路径仅连接高度差不超过 $k$ 米的空地。

详细子任务附加限制及分值如下表所示。