Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 $1\ldots N$ 的 $N$ 个检查点组成。

有 $K$ 张票可供购买。第 $i$ 张票可以在检查站 $c_i$以 $p_i$的价格购得，并且可以用其进入所有检查站 $[a_i,b_i]$。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。

对于每一个 $i \in [1,N]$，如果 Bessie 最初只能进入检查点 $i$，输出使得可以进入检查点 $1$ 和 $N$ 所需的最低总价。如果无法这样做，输出 -1。

• $1\leqslant N\leqslant 10^5$
• $1\leqslant K\leqslant 10^5$
• $1\leqslant c_i\leqslant N$
• $1\leqslant p_i\leqslant 10^9$
• $1\leqslant a_i\leqslant b_i\leqslant N$

输入格式

输入的第一行包含 $N$ 和 $K$。

以下 $K$ 行，对于每一个 $1\leqslant i \leqslant K$，第 $i$ 行包含四个整数 $c_i$，$p_i$，$a_i$ 和 $b_i$。

输出格式

输出 $N$ 行，每行输出一个检查点的答案。

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 
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\leqslant 1000$。

• 测试点 8-19 没有额外限制。

题目提供者

Benjamin Qi