问题分析

在这道题中，我们需要计算图中每个节点的不稳定性。节点的不稳定性定义为从该节点出发，到达能到达的所有节点时，节点能量的最大值与最小值的差。

每个节点的初始能量随时间的推移而下降，并且通过每条有向边需要消耗时间，导致目标节点能量的变化。节点的能量下降是一个递减过程，且能量值不能低于0。

问题拆解

1. 图的建模：给定的有向图包含n个节点和m条边，节点的初始能量为a[i]。每个节点的能量会随着时间推移而下降，下降的速率为k。我们需要通过深度优先搜索（DFS）或拓扑排序来遍历图，计算每个节点从当前节点出发能够到达的节点的能量最大值和最小值。

题目内容

$Tk$ 有一个由$n$个节点$m$条有向边组成的，节点编号为$1$~$n$的有向无环图，编号i的节点有一股强度为$a_i$的初始能量。 每过一个单位时间，所有节点的能量都会下降$k$(能量不会下降为负值，即如果有节点能量小于k时只会下降至$0$)，$Tk$经过一条边需要花费一个单位时间。

定义每个节点的不确定性，是$Tk$从此节点出发、到能到达的所有节点，到达时的最大能量减去能到达的所有节点，到达时的最小能量(无需保证最大能量节点与最小能量节点在同个简单路径)。你需要求出每个节点的不稳定性。

注意:我们认为，$Tk$到达一个点位时，先将该节点的能量按照经过时间减少$k$(但不低于 $0$)，再记录该节点的能量值。

简单路径是指这样一条路径，其经过的顶点和边互不相同。

输入描述

第一行输入三个正整数 $n,m,k(2≤n≦2×10^5;1≦m≦2×10^5;1≦k≦10^9)$代表这个有向无环图的节点数量、边的数量、每个节点单位时间下降的能量值。

第二行输入$n$个正整数$a_1,a_2,...,a_n(1≦a_i≦10^9)$表示每一个节点的初始能量。

接下来 $m$行，每一行输入两个整数$v_i,u_i(l ≦ v_i,u_i≦n,v_i≠u_i)$表示有一条节点$v_i$到节点 $u_i$的有向边，保证没有重边和自环。

输出描述

输出一行$n$个整数，第$i$个整数表示节点$i$的不稳定性

样例1

输入

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

输出

8 2 2 1 0