Constructing Edge Water Flow Rates

Given an undirected connected graph with N vertices and M edges, each vertex has a specified water change rate. On each edge, you can perform one of two operations:

• Water flowing out: Given a parameter \(d\), for an edge with length \(m\) and flow time \(s\), the total water loss rate is \(\frac{2d m^3}{s}\) and each endpoint loses water at a rate of \(\frac{d m^3}{s}\).
• Water flowing in: Given a parameter \(p\), for an edge with length \(m\) and flow time \(s\), the total water gain rate is \(\frac{2p m^3}{s}\) and each endpoint gains water at a rate of \(\frac{p m^3}{s}\).

Since the operation on an edge affects both its endpoints equally, if we let the value \(x_e\) denote the water change rate contributed by edge \(e\) to each of its endpoints then:

[ \text{For each vertex } i:\quad \sum_{e \in E(i)} x_e = b_i, ]

where \(b_i\) is the given water change rate at vertex \(i\) and \(E(i)\) is the set of edges incident on \(i\). Note that if \(x_e \ge 0\), it corresponds to the "water flowing in" operation with \(p = \frac{x_e s}{m^3}\); if \(x_e .

Your task is to construct a valid assignment \(\{x_e\}\) for every edge such that the above system holds. It is guaranteed that the input data is feasible (that is, a solution always exists). In case there are multiple solutions, you may output any one.

Input and output note: The edge parameters \(m\) (length) and \(s\) (flow time) are given for each edge. The output should be M real numbers (one for each edge in the same order as input), where the \(j\)th number is the water change rate \(x_j\) on that edge.

inputFormat

The first line contains two integers \(N\) and \(M\) (the number of vertices and edges, respectively). The second line contains \(N\) real numbers \(b_1, b_2, \dots, b_N\), where \(b_i\) is the water change rate at vertex \(i\). Then \(M\) lines follow, each describing an edge with four values: u v m s, where \(u\) and \(v\) (1-indexed) are the endpoints of the edge, \(m\) is the length of the edge, and \(s\) is the flow time.

Note: The graph is undirected and connected.

outputFormat

Output M real numbers (each formatted with at least 6 digits after the decimal point) in one line separated by spaces. The jth number is the water change rate \(x_j\) on the corresponding edge. Recall that if \(x_j \ge 0\), it means water flows in (with parameter \(p = \frac{x_j s}{m^3}\)), and if \(x_j < 0\), it means water flows out (with parameter \(d = \frac{-x_j s}{m^3}\)).

sample

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

1.000000 3.000000 2.000000