Optimal Problem Selection

You are given a total competition time T and n categories of contest problems. For each category i (1 ≤ i ≤ n), three integers are provided:

• m_i: the maximum number of problems available in category i,
• t_i: the time required to solve each problem in category i, and
• p_i: the score obtained for solving a problem in category i.

Your task is to choose a nonnegative integer k_i (0 ≤ k_i ≤ m_i) for each category such that the total solving time

[ \sum_{i=1}^{n} k_i \cdot t_i \le T ]

and the total score

[ \sum_{i=1}^{n} k_i \cdot p_i ]

is maximized. In case of multiple optimal solutions, any one is acceptable. Output the vector (k₁, k₂, \ldots, k_n) in order.

inputFormat

The first line of the input contains two integers T and n, representing the total available time and the number of categories, respectively.

Then follow n lines, each containing three integers: m_i, t_i, and p_i (for 1 ≤ i ≤ n) separated by spaces.

outputFormat

Output a single line with n integers. The i-th integer represents the number of problems chosen from category i in an optimal selection.

sample

10 2
5 2 3
3 3 4

5 0