There are $n$ cities connected by $m$ directed roads.

The length of the $i$-th road is $a_i$. If it is renovated, its length becomes $b_i$.

City $1$ is the capital, and there are $k$ provincial capitals.

You want to minimize the maximum shortest distance from the capital to any provincial capital, but you cannot renovate too many roads.

For all $x \in [0, m]$, find the minimum possible value of this maximum shortest distance after renovating exactly $x$ roads.

Input

The first line contains three positive integers $n, m, k$.

The second line contains $k$ positive integers, where the $i$-th integer $p_i$ represents the provincial capitals.

The next $m$ lines each contain four positive integers $x_i, y_i, a_i, b_i$, representing a directed road from $x_i$ to $y_i$ with lengths $a_i$ before renovation and $b_i$ after renovation.

Output

Output $m+1$ space-separated integers, representing the answers for $x = 0, 1, \dots, m$ respectively.

Examples

Input 1

3 3 2
2 3
1 2 12 5
1 3 9 8
2 3 5 2

Output 1

12 9 7 7

Note 1

Without renovating any roads, the shortest distance from $1$ to $2$ is $12$, and from $1$ to $3$ is $9$. The answer is $12$.

Renovating the first road, the shortest distance from $1$ to $2$ becomes $5$, and the answer is $9$.

Renovating the first and third roads, the shortest distance from $1$ to $3$ becomes $7$, and the answer is $7$.

Constraints

It is guaranteed that all nodes are reachable from node $1$. $k < n$, $p_i \in [2, n]$ and are distinct, $x_i, y_i \in [1, n]$, and $1 \leq b_i \leq a_i \leq 10^5$.

Multiple edges and self-loops are possible.

$n, m \leq 100, k \leq 8$.

Subtask 1 (15 pts): $n, m \leq 10$.

Subtask 2 (15 pts): $k = 1$.

Subtask 3 (15 pts): $k = 2$.

Subtask 4 (55 pts): No additional constraints.