拜特山（Góra Bajtocka）是拜特国（Bajtocja）的最高峰，有一条风景优美的步道通往山顶。步道上有 $n$ 个休息点，位于不同的高度：第 $i$ 个休息点的高度为 $i$ 拜特米。这些休息点由 $m$ 条旅游道路连接，道路通往山上（有时是绕过某些休息点的桥梁）。每个休息点都有一个整数表示的“上镜系数”（photogenicity coefficient）。

出于安全考虑，严禁离开指定的道路！该地区的天气变化极快，拜特山经常遭受强降雨。游客只能在休息点的专用遮雨棚中避雨，因此为了确保游客安全，没有任何一段道路过长——每条道路连接的两个休息点高度差不超过 $k$ 拜特米。

拜特摄影协会（BKF）的一组 $n$ 名摄影师想要前往拜特山。起初，他们计划一起爬到某个休息点 $p$。在那个休息点，他们将分开——此后每位摄影师将独立选择自己的后续路线。每位摄影师只能沿着旅游道路向上移动，并拍摄他们经过的休息点的照片。只有在休息点时才能拍照（由于技术原因，在旅游道路上移动时无法拍摄高质量的照片）。每位摄影师可以在任意选择的休息点结束他们的攀登。

最后，摄影师们将确定探险的“美感度”——即他们拍摄照片的所有休息点的上镜系数之和（对于每个休息点，他们共同最多选择一张照片）。

BKF 管理层尚未决定摄影师应从哪个休息点 $p$ 开始探险并分开。请帮助他们做出决定，并编写一个程序，对于所有可能的休息点 $p$ 的选择，计算从该休息点开始的探险所能达到的最大美感度。

输入格式

输入的第一行包含三个整数 $n, m, k$ ($2 \le n \le 100\,000, 1 \le m \le 800\,000, 1 \le k \le 8$)，分别表示休息点的数量、道路的数量以及道路的最大长度。

第二行包含一个由 $n$ 个整数组成的序列 $f_1, \dots, f_n$ ($1 \le f_i \le 10^9$)，表示各休息点的上镜系数。

接下来的 $m$ 行描述了道路：第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le n, b_i \le a_i + k$)，表示从休息点 $a_i$ 到休息点 $b_i$ 的一段道路。道路互不相同。

输出格式

你的程序应输出恰好 $n$ 行：第 $i$ 行应包含一个整数，表示如果摄影师从休息点 $p = i$ 开始探险并分开，所能达到的最大美感度。

样例

输入 1

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

输出 1

13
5
6
1

子任务

测试集分为以下子任务。每个子任务的测试用例由一个或多个独立的测试组组成。