Bajtocka Mountain is the highest peak in Bajtocja. A picturesque trail leads to its summit. There are $n$ clearings on this trail at various altitudes: the $i$-th clearing is at an altitude of $i$ bajtometers. The clearings are connected by $m$ segments of tourist paths that lead up the mountain (sometimes these are footbridges bypassing some clearings). Each clearing has its own photogenicity coefficient, expressed as an integer.

Moving outside the designated paths is prohibited for safety reasons! The weather in this region changes rapidly, and Bajtocka Mountain is often hit by intense downpours. One can only take shelter from them in special shelters located at the clearings, so to ensure the safety of tourists, no path segment is too long – each one connects clearings that differ in altitude by at most $k$ bajtometers.

A group of $n$ photographers from the Bajtocja Photographic Club (BKF) wants to go to Bajtocka Mountain. Initially, they plan to climb together to a certain clearing $p$. At this clearing, they will split up – now each photographer will independently choose their further path. Each of them will move exclusively upwards using the tourist paths and take photos of the clearings they pass through. A photo of a clearing can only be taken while being at that clearing (for technical reasons, it is impossible to take good photos while moving along the tourist paths). Each photographer can end their climb at any chosen clearing.

Finally, the photographers will determine the picturesqueness of the expedition – the sum of the photogenicity coefficients of the clearings they took photos of (where for each clearing, they will collectively choose at most one photo).

The BKF board has not yet decided from which clearing $p$ the photographers will start the expedition and split up. Help them make the decision and write a program that, for all possible choices of the clearing $p$, determines the maximum picturesqueness of an expedition starting at that clearing.

Input

The first line of the input contains three integers $n$, $m$, and $k$ ($2 \le n \le 100\,000$, $1 \le m \le 800\,000$, $1 \le k \le 8$), representing the number of clearings, the number of path segments, and the maximum length of a segment, respectively.

The second line contains a sequence of $n$ integers $f_1, \dots, f_n$ ($1 \le f_i \le 10^9$), representing the photogenicity coefficients of the successive clearings.

The next $m$ lines describe the path segments: the $i$-th of them contains two integers $a_i$ and $b_i$ ($1 \le a_i < b_i \le n$, $b_i \le a_i + k$), representing a path segment from clearing $a_i$ to clearing $b_i$. The paths are distinct.

Output

Your program should output exactly $n$ lines: the $i$-th of them should contain a single integer representing the maximum picturesqueness of the expedition if the photographers start the expedition from clearing $p = i$ and then split up.

Examples

Input 1

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

Output 1

13
5
6
1

Test cases

• Test 1: $n = 5, m = 4, k = 1; f_i = 2^{i-1}$ (for $1 \le i \le n$).
• Test 2: $n = 30, k = 2; f_i = 998244353 - 2^{i-1}$, each clearing has paths to the two next ones (if they exist).
• Test 3: $n = 1000, k = 8; f_i = i$, from each clearing there are paths to clearings whose number is not coprime to its number.
• Test 4: $n = 100\,000, k = 8; f_i = 1$, there are paths between clearings if they share a common digit in their decimal representation.
• Test 5: $n = 100\,000, k = 8$; from each clearing there are paths to clearings at an even distance.

For every test, the requirement holds that paths exist only between clearings that are at most $k$ bajtometers apart.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.