### 问题描述 小齐准备进行一次徒步远足！她当前所走的小径包含 $N$ 个检查点，分别标记为 $1...N$。 共有 $K$ 张门票可供购买。第 $i$ 张门票可以在检查点 $c_i$ 处以价格 $p_i$ 购买，允许通行所有检查点 $[a_i, b_i]$（$1 \leq a_i \leq b_i \leq N$）。在进入任何检查点之前，小齐必须购买允许通行该检查点的门票。一旦小齐可以进入某个检查点，她可以在将来的任意时刻返回到该检查点。她可以在具有通行权的两个检查点之间移动，无论它们的标签是否相邻。 对于每个 $i \in [1, N]$，输出在初始只能进入检查点 $i$ 的情况下购买通行所有检查点 $1$ 和 $N$ 所需的最小总价格。如果无法做到这一点，则输出 $-1$。 ### 输入格式 第一行包含 $N$ 和 $K$。 接下来的 $K$ 行，每行包含四个整数 $c_i, p_i, a_i, b_i$，表示第 $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 ``` ### 评测数据规模 $1 \leq N \leq 10^5$，$1 \leq K \leq 10^5$，$1 \leq c_i \leq N$，$1 \leq p_i \leq 10^9$。