题目描述

贝茜正在度假！

由于最近的科技进步，贝茜将乘坐最先进的航班旅行，有些航班甚至可以进行时间旅行。

此外，即使两个“平行”时空的贝茜相遇也没有问题。

全国共有 $N$ 个机场，编号 $1∼N$。

一共有 $M$ 个航班，航班 $j$ 在时间 $r_j$ 离开机场 $c_j$，在时间 $s_j$ 到达机场 $d_j$。

此外，每当贝茜到达机场 $i$ 后，至少需要在机场 $i$ 停留 $a_i$ 时间方可离开。

也就是说，如果贝茜乘坐某航班在时间 $s$ 到达机场 $i$，则它可以换乘某航班在时间$r$ 离开机场 $i$ 的前提是 $r≥s+a_i$。

机场停留对贝茜何时到达机场没有影响。

贝茜在时间 0 从城市 *1 出发。

对于从 1 到 $N$ 的每个机场，请你计算贝茜可以到达该机场的最早时间。

输入格式

第一行包含两个整数 $N,M$。

接下来$M$ 行，每行包含四个整数 $c_j,r_j,d_j,s_j$用来描述一个航班。

最后一行，包含 $N$ 个整数 $a_1,a_2...a_N$。

输出格式

共 $N$ 行，其中第 $i$ 行输出贝茜可以到达 $i$ 的最早时间，如果贝茜无法到达该机场，则输出 -1。

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

0
0
20

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

0
10
-1

数据范围

$1≤N,M≤2×10^5,$
$1≤c_j,d_j≤N,$
$0≤r_j,s_j≤10^9,$
$s_j<r_j$ 是有可能的。
$1≤a_i≤10^9$。

样例1解释

贝茜可以按顺序依次乘坐 3 个给定航班，这可以让它在时间 0 到达机场 1,2，在时间20 到达机场 3。

注意，这个行进路线的过程中在机场 2 停留了两次，第一次停留是时间10−11，第二次停留是时间 0−1。

样例2解释

在本样例中，贝茜可以乘坐第 1 个航班并于时间 10 到达机场 2。

然后它必须在机场 2 停留时间1，因此它无法乘坐第 2 个航班，继而也无法乘坐第3 个航班。