Format

有一个数列 \(a\)，满足以下 \(2\) 条限制：

* 对于 \(1 \le i \le q\)，\(l_i \le \sum_{i=L_i}^{R_i}{a_i} \le r_i\)
* 对于 \(1\le k \le n\)，\(\sum_{i=1}^k a_i \le 10^{12}\)，允许有负数，但不能超过 long long值域。

给出 \(q\) 条限制，构造一个 \(a\) 满足条件且字典序最大。

Input

第一行两个数 \(n\)，\(q\)。
第 \(i + 1\) 行 \(4\) 个数，分别表示 \(L_i,R_i,l_i,r_i\)。

Output

一行 \(n\) 个数，表示构造出的 \(a\)。

数据保证有解。

Sample 1

Input

2 3
1 1 1 2
2 2 1 2
1 2 4 100

Output

2 2

Sample 2

Input

4 4
2 4 -79 26
1 3 -67 25
1 3 -16 10
2 3 -49 39

Output

59 999999999941 -999999999990 75

Sample 3

Input

3 3
1 1 2 3
1 2 4 5
1 2 6 7

Output

-1

Limitation

对于所有数据，\(a_i \le 10^{12}\)，\(0 \le l_i,r_i \le 10^9\)，\(1 \le L_i \le R_i \le n\)

Subtask 编号	\(n \times q \le \)	\(\max a_i \le \)	Score
1	16	10	10
2	500	1000	20
3	2e5	1e7	25
4	1e6	1e9	45