Мішки з числами

Limits: 2 sec., 256 MiB

У Зеника і Марічки є \(n\) початково пустих мішків для чисел, розміщених в ряд та пронумерованих від 1 до \(n\) включно.

Вони послідовно \(m\) разів виконували наступну операцію: до усіх мішків від \(l_i\)-го до \(r_i\)-го (включно) додати число \(d_i\) (\(1 \le i \le m\)).

Після виконання усіх операцій вам потрібно для кожного мішка вивести значення медіани чисел, які містяться в ньому, або -1, якщо мішок пустий. Зауважте, що мішки можуть містити більше одного входження однакового числа.

Медіаною послідовності чисел \(a_1, a_2, ..., a_k\) будемо вважати \(\left \lceil{\frac{k+1}{2}}\right \rceil\)-те найменше з них.

Input

У першому рядку задано два цілих числа \(n\) та \(m\) — кількість мішків та виконаних операцій.

У наступних \(m\) рядках задано по три цілих числа \(l_i\), \(r_i\) та \(d_i\), які описують виконані операції.

Output

У єдиному рядку виведіть \(n\) цілих чисел — шукане значення для відповідного мішка.

Constraints

\(1 \le n, m \le 10^5\),

\(1 \le l_i \le r_i \le n\),

\(1 \le d_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 1 3 4 2 6 7 3 3 5 5 6 11	4 7 5 7 11 11 -1

Notes

Після виконання операцій мішки будуть містити наступні числа (жирним позначено медіану):

1. 4

2. 4 7

3. 4 5 7

4. 7

5. 7 11

6. 7 11

7. (пустий мішок)