Xiaoqiang and B are good friends. Xiaoqiang has many other good friends besides B, such as Jiemei. B has many other good friends besides Xiaoqiang, such as R. They also have many mutual friends, such as Xiaohua, Congniang, and 3 others.

B discovers that the relationships between people can be viewed as an undirected graph, where each person is a vertex and each relationship is an edge.

Different people have different levels of influence in society; we use $a_i$ to represent the influence of the $i$-th person. Relationships between people also vary; some are very friendly, while others are mere acquaintances; some may be together every day, while others may only contact each other once a year. For this reason, we use a length edge weight $b_j$ to characterize the intimacy between the two users corresponding to the $j$-th edge; the smaller the length, the more intimate the two parties are. At the same time, we use a width edge weight $c_j$ to characterize the communication frequency between the two users corresponding to the $j$-th edge; the larger the width, the higher the frequency of communication between the two.

The length of a path is defined as the sum of the length edge weights of all edges on this path, and the width of a path is defined as the product of the width edge weights of all edges on this path.

When two people $s$ and $t$ want to communicate, they will choose the path with the shortest length. Since there may be multiple shortest paths, we call the width of the shortest path from $s$ to $t$, denoted as $\sigma_{st}$, the sum of the widths of all shortest paths from $s$ to $t$. At the same time, we use $\sigma_{st}(v)$ to denote the sum of the widths of all shortest paths from $s$ to $t$ that pass through vertex $v$, which represents the influence of $v$ on $s, t$.

The propagation power $R(v)$ of a person $v$ in the graph can be defined by the following function:

$$R(v) = \sum_{s \neq v \neq t} \frac{a_s a_t \sigma_{st}(v)}{\sigma_{st}}$$

That is, for all pairs of points in the graph that do not contain $v$, calculate the influence of $v$ on that pair divided by the width of the shortest path for that pair, then multiply by the product of the influence of the two points in the pair, and finally sum the calculation results of all pairs to obtain the propagation power of the node in the graph.

B wants to quickly know the propagation power of all nodes in the graph. When he asked Xiaoqiang, Xiaoqiang said: "I have a brilliant method, but the problem statement is too short to write it down." Do you know how to do it?

Input

The first line of the input file contains two positive integers $n$ and $m$, representing the number of vertices and edges in the graph, respectively. The next $n$ lines, the $i$-th line contains one non-negative integer $a_i$, representing the influence of the $i$-th person. The next $m$ lines, the $j$-th line contains three integers $x_j, y_j, b_j$ and one real number $c_j$, representing an edge between point $x_j$ and point $y_j$ with a length edge weight of $b_j$ and a width edge weight of $c_j$.

Output

The output file contains $n$ lines, each containing a real number $R(i)$, representing the propagation power of the $i$-th point in the graph.

Examples

Input 1

5 5
1 2 3 4 5
1 2 2 0.7
3 4 2 0.9
1 3 1 1.1
2 4 1 1.3
4 5 10 2

Output 1

4.762887
8.621053
9.378947
67.237113
0.000000

Input 2

See misc/misc.in and misc/misc.ans in the contestant directory.

Note

We will compare each number in the output file with the reference answer. If the relative error or absolute error between the number and the reference answer does not exceed $10^{-6}$, the number is considered correct. For numbers where the reference answer is $0$, the absolute error must not exceed $10^{-6}$ to be considered correct.

If the number of correctly output values is $q$, then your score on this test case is:

$$\left\lfloor 5 \left( \frac{q}{n} \right)^7 \right\rfloor$$

Constraints

For test cases 1, 2, 3, 4, $n \le 100$. For test cases 5, 6, 7, 8, all $b_j = 1$. For test cases 9, 10, 11, 12, $m = n - 1$. For test cases 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, all $a_i = 1$. For test cases 1, 2, 5, 6, 9, 10, 13, 14, 17, 18, all $c_j = 1$. For all data, $n \le 1000$, $m \le 4000$, $0 < a_i \le 255$, $0 < b_j \le 15$, $0.5 \le c_j \le 2$. The decimal part of $c_j$ has at most 12 digits. The graph is guaranteed to be connected.