[USACO21DEC] Tickets P
题目描述
Bessie 正在参加远足旅行!她当前正在旅行的路线由编号为 $1\ldots N$($1\le N\le 10^5$)的 $N$ 个检查点组成。
有 $K$($1\le K\le 10^5$)张票可供购买。第 $i$ 张票可以在检查站 $c_i$($1\le c_i\le N$)以 $p_i$($1\le p_i\le 10^9$)的价格购得,并且可以用其进入所有检查站 $[a_i,b_i]$($1\le a_i\le b_i\le N$)。在进入任何检查站之前,Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站,她就可以在未来的任何时候回到该检查站。
对于每一个 $i\in [1,N]$,如果 Bessie 最初只能进入检查点 $i$,输出使得可以进入检查点 $1$ 和 $N$ 所需的最低总价。如果无法这样做,输出 $-1$。
输入输出格式
输入格式
输入的第一行包含 $N$ 和 $K$。
以下 $K$ 行,对于每一个 $1\le i\le K$,第 $i$ 行包含四个整数 $c_i$,$p_i$,$a_i$ 和 $b_i$。
输出格式
输出 $N$ 行,每行输出一个检查点的答案。
输入输出样例
输入样例 #1
7 6
4 1 2 3
4 10 5 6
2 100 7 7
6 1000 1 1
5 10000 1 4
6 100000 5 6
输出样例 #1
-1
-1
-1
1111
10100
110100
-1
说明
【样例解释】
如果 Bessie 从检查点 $i=4$ 开始,那么一种购得进入检查点 $1$ 和 $N$ 的方法如下:
在检查点 $4$ 购买第一张票,使 Bessie 可以进入检查点 $2$ 和 $3$。
在检查点 $2$ 购买第三张票,使 Bessie 可以进入检查点 $7$。
回到检查点 $4$ 购买第二张票,使 Bessie 可以进入检查点 $5$ 和 $6$。
在检查点 $6$ 购买第四张票,使 Bessie 可以进入检查点 $1$。
【数据范围】
- 测试点 1-7 满足 $N,K\le 1000$。
- 测试点 8-19 没有额外限制。