Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 1…N（1≤N≤10^5）的 N 个检查点组成。 有 K（1≤K≤10^5）张票可供购买。第 i 张票可以在检查站 ci（1≤ci≤N）以 pi（1≤pi≤109）的价格购得，并且可以用其进入所有检查站 [ai,bi]（1≤ai≤bi≤N）。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。对于每一个 i∈[1,N]，如果 Bessie 最初只能进入检查点 i，输出使得可以进入检查点 1 和 N 所需的最低总价。如果无法这样做，输出 −1。

输入的第一行包含 N 和 K。 以下 K 行，对于每一个 1≤i≤K，第 i 行包含四个整数 ci，pi，ai 和 bi。

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

样例说明 如果 Bessie 从检查点 i=4 开始，那么一种购得进入检查点 1 和 N 的方法如下：

在检查点 4 购买第一张票，使 Bessie 可以进入检查点 2 和 3。 在检查点 2 购买第三张票，使 Bessie 可以进入检查点 7。 回到检查点 4 购买第二张票，使 Bessie 可以进入检查点 5 和 6。 在检查点 6 购买第四张票，使 Bessie 可以进入检查点 1。

数据规模 测试点 1-7 满足 N,K≤1000。 测试点 8-19 没有额外限制。