有 $n$ 个城市，用 $m$ 条单向道路连接。

第 $i$ 条道路的长度是 $a_i$，如果对其进行翻修，则长度变为 $b_i$。

$1$ 号城市是首都，有 $k$ 个省会城市。

你希望首都到省会城市的最短距离的最大值尽可能小，但是你不能翻修太多道路。

对于所有 $x\in[0,m]$ 求出翻修 $x$ 条道路之后最小的最大值。

输入格式

第一行三个正整数 $n,m,k$。

第二行 $k$ 个正整数，第 $i$ 个 为 $p_i$，表示所有省会城市。

接下来 $m$ 行，第 $i$ 行四个正整数 $x_i,y_i,a_i,b_i$ 表示 $x_i$ 到 $y_i$ 有一条单向道路，翻修前后长度为 $a_i,b_i$。

输出格式

一行 $m+1$ 个正整数，分别表示 $x=0,1\cdots m$ 时的答案。

样例输入

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

样例输出

12 9 7 7

样例解释

不翻修道路，$1$ 到 $2$ 的最短距离为 $12$，$1$ 到 $3$ 为 $9$，答案为 $12$。

翻修第一条道路，$1$ 到 $2$ 的最短距离变为 $5$，答案为 $9$。

翻修第一条和第三条道路，$1$ 到 $3$ 的最短距离变为 $7$，答案为 $7$。

数据范围

保证从 $1$ 号点出发能到达所有点，$k< n$,$p_i\in[2,n]$ 且互不相同，$x_i,y_i\in[1,n]$，$1\leq b_i\leq a_i \leq 10^5$。

不保证无重边自环。

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

Subtask 1（15pts）：$n,m\leq 10$。

Subtask 2（15pts）：$k=1$。

Subtask 3（15pts）：$k=2$。

Subtask 4（55pts）：无特殊限制。

时间限制：1s。

空间限制：256MB。