... and the girl who crossed the moon's oceans. — Frums

You are given an undirected graph consisting of $n$ vertices and $m$ edges. The $i$-th vertex has an associated value $\mathrm{val}_i$. The $j$-th edge connects vertices $u_j$ and $v_j$ and has two properties: a capacity $w_j$ and a floor $\mathrm{low}_j$. It is guaranteed that $w_j \ge \mathrm{low}_j$ for all edges.

You want to start a walk from a vertex $s$. Before the walk begins, you must choose an arbitrary non-negative integer $h_{start}$ as your initial state parameter.

If you are currently at vertex $u$ with state $h$, you can traverse an edge $j$ connecting $u$ and $v$ if and only if $w_j \ge h$. Upon traversing this edge and arriving at vertex $v$, the state parameter $h$ updates to $\max(h, \mathrm{low}_j)$.

Let the walk end at some vertex $t$. You must traverse at least one edge. The score of such a walk is defined as $\mathrm{val}_t + h_{start}$. Note that we are interested in the sum of the final vertex value and the initial state parameter, not the final state parameter.

For each starting vertex $s$ from $1$ to $n$, calculate the maximum possible score achievable. If it is impossible to traverse any edge starting from some $s$, output $-1$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 5\cdot 10^5, 0 \le m \le 5\cdot 10^5$) — the number of vertices and the number of edges.

The second line of each test case contains $n$ integers $\mathrm{val}_1, \mathrm{val}_2, \ldots, \mathrm{val}_n$ ($1 \le \mathrm{val}_i \le 10^9$) — the values of the vertices.

The next $m$ lines describe the edges. The $j$-th line contains four integers $u_j, v_j, w_j, \mathrm{low}_j$ ($1 \le u_j, v_j \le n, u_j \neq v_j$; $1 \le \mathrm{low}_j \le w_j \le 10^9$) — the endpoints and properties of the $j$-th edge.

The graph is not guaranteed to be connected and may contain multiple edges.

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $5\cdot 10^5$.

Output

For each test case, output $n$ integers separated by spaces. The $i$-th integer should be the maximum score achievable starting from vertex $i$, or $-1$ if no edge can be traversed.

Note

In the first test case, here are the optimal $h_{start}$ values and paths for each starting node:

• For node $1$, it is optimal to use $h_{start}=5$. Then, take the path from node $1$ to node $2$. $h$ is updated to $\operatorname{max}(5,2)=5$. The path ends, and the score is $20+5=25$.
• For node $2$, it is optimal to use $h_{start}=5$. Then, take the path from node $2$ to node $1$, then from node $1$ to node $2$. The score is $20+5=25$.
• For node $3$, it is optimal to use $h_{start}=4$. Then, take the path from node $3$ to node $2$. The score is $20+4=24$.

In the third test case, since there are no edges incident to either node, the answer is $-1$ for both.