Optimal Gym Equipment Scheduling

There is a gym with \(k\) pieces of equipment. There are \(n\) people making reservations for workouts. The \(i\)th person makes a reservation by specifying three integers \(l_i, r_i, p_i\). This means that this person may be assigned an hour \(x\) where \(l_i \le x \le r_i\) and will work out using the equipment numbered \(p_i\) during hour \(x\).

It is not allowed to have two people use the same equipment at the same time (i.e. if two reservations share the same equipment, they must be scheduled in different hours). On the other hand, the gym owner wishes to have as many idle hours as possible (i.e. the set of hours during which no reservation is scheduled is as large as possible). Equivalently, if we let \(H=\{x : x \text{ is assigned to at least one reservation}\}\), the owner wants \(|H|\) to be as small as possible.

Your task is to assign an hour \(x_i\) (an integer) for each reservation so that:

• For every reservation \(i\), \(l_i \le x_i \le r_i\).
• If two reservations \(i\) and \(j\) have the same equipment (i.e. \(p_i = p_j\)) then \(x_i \neq x_j\).
• The total number of distinct hours used (i.e. \(|\{x_1,x_2,\ldots,x_n\}|\)) is minimized.

You may assume that the number of reservations and the range of allowable hours are small, so that an algorithm which tries all candidate sets of hours is acceptable.

Note: If there are several optimal solutions, any one of them is acceptable.

The allowed hours are assumed to be integers. In case a reservation cannot be scheduled according to these rules, you may assume that such a situation will not occur in the test data.

inputFormat

The input begins with a line containing two integers \(k\) and \(n\) (\(1 \le k \le n\)). Each of the next \(n\) lines contains three integers \(l_i, r_i, p_i\) representing a reservation: the reservation allows any integer hour \(x\) with \(l_i \le x \le r_i\), and the reservation is for equipment number \(p_i\) (\(1 \le p_i \le k\)).

You may assume that \(l_i, r_i\) are positive integers and that \(l_i \le r_i\). Also, all test cases guarantee that there exists at least one valid assignment.

outputFormat

Output \(n\) lines. The \(i\)th line should contain one integer \(x_i\), which is the scheduled hour for the \(i\)th reservation (in the same order as input). The assignment must obey the reservation constraints and minimize the number of distinct hours used.

sample

2 3
2 3 1
2 2 1
2 2 2

3
2
2