Byteasar 是一位负责码头的土木工程师。码头呈长条状，可以看作是从 $1$ 到 $n$ 编号的 $n$ 个连续位置。起重机可以在给定的位置堆放任意数量的集装箱，使它们一个叠在另一个上面。

各种货物都存放在集装箱中。特别是，存放危险品或极其贵重货物的集装箱为了安全起见需要间隔放置。

Byteasar 收到了起重机即将执行的 $k$ 个操作列表：第 $i$ 个操作编码为 $(a_i, \ell_i, d_i)$，这意味着起重机将从位置 $a_i$ 开始，每隔 $d_i$ 个位置放置 $\ell_i$ 个集装箱，即在位置 $a_i, a_i + d_i, a_i + 2d_i, \dots, a_i + (\ell_i - 1)d_i$ 处各放置一个集装箱。Byteasar 想知道在执行完所有列出的操作后，每个位置上的集装箱最终数量是多少。

输入格式

标准输入的第一行包含两个正整数 $n$ 和 $k$，分别表示码头沿线的位置数量和起重机操作的数量。接下来的 $k$ 行描述了这些操作：第 $i$ 行包含三个正整数 $a_i, \ell_i$ 和 $d_i$，满足 $a_i + (\ell_i - 1)d_i \le n$。你可以假设当 $\ell_i = 1$ 时，$d_i = 1$。

输出格式

输出一行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 应等于所有起重机操作完成后位置 $i$ 上的集装箱数量。

样例

样例输入 1

8 3
3 4 1
2 3 3
3 2 2

样例输出 1

0 1 2 1 3 1 0 1

集装箱上的数字对应于将其放置在码头上的操作编号。

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试组。