题目背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

23333 年，在经过长时间的建设后，一个庞大的星际网络终于初具规模。星际网络共接入了 $n$ 颗星球，由 $m$ 颗中继卫星来实现星球之间的互联互通。所有星球之间的通信都必须经由一颗或多颗中继卫星来实现，星球本身也可以起到中继的作用，如果两颗星球的距离很远，数据可以沿“星球——中继卫星——星球——中继卫星——...——星球”的模式进行传输。

对于每一颗中继卫星而言，可以与多颗距离上较为接近的星球通信，但由于卫星结构的设计原因，通信只能单向进行。具体而言，第 $i$ 颗中继卫星可以接收编号在 $[l_{1i}, r_{1i}]$ 范围内的星球发送来的数据，并向编号在 $[l_{2i}, r_{2i}]$ 范围内的星球发送数据。

数据在星际之间传输的延迟当然是惊人的。为简单起见，我们假设这一延迟只由数据经过的中继卫星决定，即数据从不同的星球发出，经同一个中继卫星，到达不同的星球，所需的延迟时间总是相同的。对于第 $i$ 颗中继卫星，数据经由该中继卫星传输所需的延迟时间约为 $T_i$ 秒。由于这个数字实在太过巨大，而且对于星际间通信的延迟估计总是充满了各种不准确因素，我们只关心其若干位有效数字，具体而言将给出二元组 $(a_i, b_i)$，表示 $T_i = a_i \times 2^{b_i}$。我们假设数据在其他位置的延迟均可忽略。实际传输中，数据从源星球发出，经由很多颗中继卫星和星球最终到达目的星球，则总延迟为过程中经过的所有中继卫星的延迟之和。

数据从某个星球出发到达另一个星球，其在中继卫星和星球之间所经过的传输路径可能是多种多样的。与普通的计算机网络类似，我们需要设计相应的路由算法来选择合适的传输路径。一种直观的方案是最小延迟原则，即数据总是会选择总延迟时间最小的传输路径。

星际网络建成后，工程师们希望通过类似于计算机网络中 ping 的方法来测试该网络。从星球 A 向星球 B 发起一次 ping 的经过如下：首先从星球 A 发送请求数据，数据经星际网络传输至星球 B，星球 B 随即发送回复数据，经星际网络传输至星球 A，星球 A 计算从它发出请求到收到回复的所经时间，称为此次 ping 的响应时间。如果星际网络结构有缺陷，使得星球 A 发出的请求无法到达星球 B，或星球B发出的回复无法到达星球 A，则星球 A 在等待足够长时间后会得到“请求超时”的结果。

现在需要从 1 号星球向其他所有星球依次发起一次 ping，假设所有数据的传输均遵循最小延迟原则，请你计算出每次 ping 的响应时间。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$。

接下来 $m$ 行：每行包含 6 个非负整数 $l_{1i}, r_{1i}, l_{2i}, r_{2i}, a_i, b_i$，描述一颗中继卫星，具体含义如上所述。

输出格式

输出到标准输出。

输出一行包含 $n - 1$ 个整数，第 $i$ 个整数表示星球 1 向星球 $i + 1$ 发起 ping 的响应时间，答案对 $10^9 + 7$ 取模后输出。

特别地，如果某次 ping 的结果为请求超时，请输出 -1。

5 5
1 2 2 3 1 2
2 2 1 1 3 0
2 3 4 5 1 1
3 3 4 4 1 0
4 4 1 2 1 0

7 6 6 -1

3 2
1 2 1 2 999999999 34
2 3 2 3 987654321 12

122094981 986235983

提示

样例 1 解释

从 1 号星球到 2 号星球的请求数据最小延迟为 $4$，2 号星球的回复数据最小延迟为 $3$。

从 1 号星球到 3 号星球的请求数据最小延迟为 $4$，3 号星球的回复数据最小延迟为 $2$。

从 1 号星球到 4 号星球的请求数据最小延迟为 $5$，4 号星球的回复数据最小延迟为 $1$。

从 1 号星球到 5 号星球的请求数据最小延迟为 $6$，5 号星球的回复数据无法到达 1 号星球。

数据范围

对于所有数据保证：$n \leq 10^5, m \leq 10^5, 1 \leq l_{1i} \leq r_{1i} \leq n, 1 \leq l_{2i} \leq r_{2i} \leq n, 1 \leq a_i \leq 10^9, 0 \leq b_i \leq 10^5$。

::cute-table{tuack}

测试点编号	$n \leq$	$m \leq$	$b_i \leq$	特殊性质
$1$	$10$		$0$	无
$2 \sim 3$	$100$		^	^
$4 \sim 5$	$1000$
$6 \sim 8$	$10^5$			$l_{1i} = r_{1i}, l_{2i} = r_{2i}$
$9 \sim 10$	^			$l_{1i} = r_{1i}$
$11 \sim 13$				无
$14 \sim 15$	$100$			^
$16 \sim 17$	$1000$
$18 \sim 20$	$10^5$			$l_{1i} = r_{1i}, l_{2i} = r_{2i}$
$21 \sim 22$	^			$l_{1i} = r_{1i}$
$23 \sim 25$				无