Minimum Chocolate Purchases with Ticket Exchanges

You are given n people and you want to give each one a chocolate. Initially, when you purchase one chocolate, you automatically receive a ticket. In addition, there are m types of exchange operations available. For each exchange type, you can exchange a_i tickets to receive b_i chocolates; note that each of these b_i chocolates comes with a ticket.

Determine, for every i from 1 to n, the minimum number of chocolates you must purchase initially in order to eventually have at least i chocolates after performing any number of exchanges.

The exchange operation can be applied repeatedly and in any order, and the same exchange type may be used multiple times if you have enough tickets. Formally, if you have x tickets at some stage and you perform an exchange of type i (with cost a_i and reward b_i), then after the exchange you will have x - a_i + b_i tickets and your total number of chocolates increases by b_i.

Your task is to compute the minimum initial purchase needed so that, after a sequence of exchanges, the total number of chocolates is at least k for each k from 1 to n.

The answer for each k can be computed using the recurrence in which you either directly purchase the chocolate (with cost 1 per chocolate) or obtain additional chocolates by performing an exchange. That is, if we define a function dp(x) as the minimum initial purchase required to obtain at least x chocolates, then we have:

$$dp(x) = \min\Bigl\{ x, \min_{1 \le i \le m} \bigl\{ dp(\max(0, x - b_i)) + a_i \bigr\} \Bigr\}. $$

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10^4 (or appropriate bound) and 1 ≤ m ≤ 10^4), representing the number of people and the number of exchange operations, respectively.

The following m lines each contain two integers a_i and b_i (1 ≤ ai, bi ≤ 10^4), which represent an exchange: you may exchange a_i tickets to obtain b_i chocolates (each carrying one ticket).

outputFormat

Output n integers separated by spaces. The i-th integer represents the minimum number of chocolates you need to purchase initially in order to eventually have at least i chocolates.

sample

5 1
3 5

1 2 3 3 3

</p>