A hotel has N rooms numbered from 1 to N. One day, M guests numbered from 1 to M according to their importancy (this is, client 1 is more important than client 2). The hotel's a good hotel, so it always has more rooms than clients, so everybody can have a room.
However, the price of a room depends in the room number and the client staying in it. For example: guest 1 would pay $100 for room 1, $50 for room 2, $90 for room 3 and so on. That way, each client has his own price list for all the hotel rooms.
Since clients have a hierarchy, the client with the lowest number is the most important, so he must go to a room that has a lower number than the rest of the clients (due to how close the room is to the restaurant). That happens too with the rest of the clients, they must go to a room with lesser number than the clients with less importance.
The hotel manager must allow them all to stay in the hotel, but he wishes to get as most profit as possible, but respecting hierarchy and allowing every guest in the hotel.
The input file, HOTEL.IN , has in its first line, the number N and the number M (M < N and N <= 200), after that, there are MxN lines with three numbers, the first one is the room number, the second one is the client's number and the last one is the corresponding fee for that room for that client.
The output file, HOTEL.OUT , must have N lines, wach one with a number indicating the number of the client which is staying in that room, or 0 if that room stays free. This configuration report must lead to a maximum profit.
NOTE: if there is more than one possible configuration that leads to the same maximum profit, any one of these configurations will be marked as valid.
SAMPLE INPUT: HOTEL.IN
3 2
1 1 100
2 2 50
3 1 30
3 2 60
2 1 40
1 2 50
SAMPLE OUTPUT: HOTEL.OUT
1
0
2
Taken from OCC. February 2001
