Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

D. Weighting a Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 1, c 2, ..., 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 2 and n 2 (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 ≤ 105, n - 1 ≤ m ≤ 105) — the number of vertices and the number of edges.

The next line contains n integers c 1, c 2, ..., 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 2 ≤ w i ≤ 2·n 2).

Examples
Input
3 32 2 21 22 31 3
Output
YES111
Input
4 3-1 0 2 11 22 33 4
Output
YES-111
Input
6 63 5 5 5 1 51 43 24 34 53 55 6
Output
YES353-1-35
Input
4 44 4 2 41 22 33 44 1
Output
NO