Bessie 正在进行一次徒步旅行！她目前所处的路径由 $N$ 个检查点组成，编号为 $1 \dots N$ ($1 \le N \le 10^5$)。

共有 $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$ 行，每行包含四个整数 $c_i, p_i, a_i, b_i$，分别对应 $1 \le i \le K$。

输出格式

输出 $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$ 开始，那么 Bessie 获得检查点 $1$ 和 $N$ 访问权限的一种方式如下：

1. 在检查点 $4$ 购买第一张票，使 Bessie 获得检查点 $2$ 和 $3$ 的访问权限。
2. 在检查点 $2$ 购买第三张票，使 Bessie 获得检查点 $7$ 的访问权限。
3. 返回检查点 $4$ 并购买第二张票，使 Bessie 获得检查点 $5$ 和 $6$ 的访问权限。
4. 在检查点 $6$ 购买第四张票，使 Bessie 获得检查点 $1$ 的访问权限。

子任务

• 测试点 1-7 满足 $N, K \le 1000$。
• 测试点 8-19 无额外限制。

题目来源：Benjamin Qi