As you know, every university has a hotel but it is always hard to book a room. Every year, thousands of orders fly to the hotels. The boss of a hotel in S University is busy, and hopes to make a program to deal with the orders. As he knows you are good at programming, he turns to you for help. The problem is described as follows:
We need to deal with the orders in the following n days. During the n days, there will be ri rooms available. And there are orders, every order is described by 3 integers, which are dj, sj, tj respectively. This indicates the customer need to book dj rooms from day sj to tj (inclusive). To simplify, we need not to care whether the customer get the same room everyday.
The principle for booking rooms is First come, First get, i.e., we need to assign rooms for the customers by the chronological sequence of the orders. If any one order can’t be satisfied, we need to stop assignment and inform the customer to modify the order. Here, the dissatisfaction refers to that at least one day during day sj to tj the number of remaining rooms is less than dj.
Now we need to know, whether there are orders can't be satisfied. And if so, we should inform which customer to modify the order.