Problem I
Road Block

Cattis and her dog also live in Bikelona. They think that it is a shame that the BIKEA employees are so stressed out and always have to take the shortest path to work. So Cattis decides to block one road in town, so that some people will have to take a longer route. That way, the cyclists will have more time to reflect and find inner peace.

Bikelona can be represented as an undirected graph with $N$ vertices and $M$ edges. The BIKEA headquarters are situated in vertex $1$. There are $x_v$ BIKEA employees living in vertex $v$, for every $v$. Your task is to find, for each edge in the graph, how many people are forced to take a longer path from their home to vertex $1$, if that edge is removed. Not being able to get to work at all also counts as having to take a longer path.

Input

The first line of input contains the two integers $N$ and $M$ ($2 \leq N \leq 3 \cdot 10^5$, $1 \leq M \leq 3 \cdot 10^5$).

The second line of input contains the $N$ integers $x_v$ ($0 \leq x_v \leq 10^9$). $x_1$ will always be $0$, because no one lives and works in the same place.

The following $M$ lines each contain two integers $u_i, v_i$ ($1 \leq u_i, v_i \leq N$), meaning that an edge goes between vertices $u_i$ and $v_i$.

The graph will always be connected, and contains no self-loops or multiple edges.

Output

Print $M$ lines with one integer $y_e$ on each, the number of people who are forced to take a longer route if the edge $e$ is removed. The edges are numbered from $1$ to $M$ in the order in which they appear in the input.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

4 4
0 10 3 7
1 2
2 3
2 4
3 4

20
3
7
0

5 6
0 1 2 100 100
1 2
1 3
2 4
2 5
3 4
3 5

1
2
0
0
0
0