You are given a connected undirected graph with n vertices and m edges. The vertices are enumerated from 1 to n.

You are given n integers c₁, c₂, ..., c_n, each of them is between - n and n, inclusive. It is also guaranteed that the parity of c_v equals the parity of degree of vertex v. The degree of a vertex is the number of edges connected to it.

You are to write a weight between - 2·n² and 2·n² (inclusive) on each edge in such a way, that for each vertex v the sum of weights on edges connected to this vertex is equal to c_v, or determine that this is impossible.

Input

The first line contains two integers n and m (2 ≤ n ≤ 10⁵, n - 1 ≤ m ≤ 10⁵) — the number of vertices and the number of edges.

The next line contains n integers c₁, c₂, ..., c_n ( - n ≤ c_i ≤ n), where c_i is the required sum of weights of edges connected to vertex i. It is guaranteed that the parity of c_i equals the parity of degree of vertex i.

The next m lines describe edges of the graph. The i-th of these lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n; a_i ≠ b_i), meaning that the i-th edge connects vertices a_i and b_i.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

Output

If there is no solution, print "NO".

Otherwise print "YES" and then m lines, the i-th of them is the weight of the i-th edge w_i ( - 2·n² ≤ w_i ≤ 2·n²).

Weighting a Tree

Examples