J. A lot of time
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dragon supposed that not all courses and trainings are so good. But he supposed that sport is good for sure. Of course, with no "cyber" prefix. He has witnessed how one gets addicted to computer games. Although he agreed that a computer game is an interesting pastime, it wastes too much time, in his opinion.

Then Dragon caught himself thinking, that communication with Prince was not in vain — it would seem, why should Dragon bother about how much time one spends playing computer games? Dragon, who exists outside of time...

Once upon a time Dragon watched a knight who was a computer game fan. That knight even organized a club of game fans. Initially, there were n gamers in the club.

When the knight wants to play, he selects a type of a game and sends invitation messages to his friends from the club. Then, these friends send messages to their friends, etc. So information about forthcoming game is spread among clubmates.

Amongst other things, a type of a game specifies its duration. It is worth noting that each of clubmates has their own opinion about how long can a game last at most. Therefore when a clubmate received an invitation for a too long game, he considers it inapropriate and removes himself from a mailing list forever and does not send any invitations to anybody. Otherwise, an invitation is considered apt and the clubmate plays a game.

Dragon is interested in how many man-minutes were spent on each game offered by the knight. Your task is to compute the values.

Input

The first line contains integers n, m, p (2 ≤ n ≤ 105,  1 ≤ m ≤ 2·105,  1 ≤ p ≤ 2·105) — initial number of clubmates, number of pairs of clubmates who are friends, and number of games which were offered by the knight.

The second line contains n - 1 integers t2, t3, ..., tn (1 ≤ tj ≤ 109) — maximum allowed duration of a game for jth clubmate. The numbering of clubmates starts with 1, and the knight has number 1 and is going to play a game of any duration.

The third line contains p integers g1, g2, ..., gp (1 ≤ gk ≤ 109) — durations of games in the same order as the games themselves.

Each of the next m lines contains two integers — numbers of clubmates who are able to send messages to each other.

Output

In the single line print p integers s1, s2, ..., sp, where sk — the total amount of time, which all gamers spent on kth game.

Examples
Input
4 4 4
2 3 3
1 3 4 1
1 2
1 3
3 4
2 4
Output
4 9 4 1
Input
4 3 1
1 10 3
3
1 2
2 3
1 4
Output
6
Note

Let us explain the samples.

In the first sample, the following occurs. All clubmates take part in the first game, so the total amount of time is 4.

When the clubmate number 2 receives an invitation to the 2nd game, he leaves the club, and only 3 gamers participate in the second game. The total amount of time is 9.

Before the 3rd game, clubmates number 3 and 4 leave the club, and only the knight participates in the 3rd game. Therefore he plays the game number 4 alone. The total amount of time is 1 for the 4th game.

In the second sample clubmate number 2 refuses to participate in the first game; so he does not send message about the game to the clubmate number 3. Since clubmate number 3 can learn about forthcoming game only from clubmate number 2, then clubmate with 3 cannot participate in this game, too. So two clubmates were participating in the game, and the total amount of time is 6.