Description
Hodilo is a well-known hot pot restaurant, and it's extremely challenging to have a table during peak dining hours in Hodilo. Even though, the restaurant does not accept reservations in advance, requiring every guest to visit the restaurant, take a number, and wait for their turn. Hodilo is opening a new branch in Hsinchu, and you have been invited to design a queuing system, which helps assign a table to each guest.
The provided data consists of the arrival record of each guest at the restaurant. Each guest's arrival time is unique. We will add them to the waiting list one by one and subsequently assign tables to the guests on the waiting list. Here's how we assign guests from the waiting list to tables:
- We will sort the waiting list based on the order in which guests arrive.
- Whenever a new guest arrives or some occupied tables are released, the following procedure is performed to see if any table assignment is possible:
if the first guest on the waiting list can be accommodated
assign the smallest table that can accommodate the guest;
else if some other guests on the waiting list can be accommodated
select the guest with the largest group size, and again assign the smallest table that can accommodate the guest;
(if multiple guests have the same largest group size, we will follow the original ordering rule (arrival time) to determine priority;)
else break;
}
Since we have access to the latest AI technology, we can accurately estimate the dining duration for each customer. By utilizing this information, we can determine the length of time each customer will occupy their table. As soon as a guest's dining time ends, we assume that the table can be cleared instantly, making it available immediately.
Your task is to assist Hodilo in implementing this system and provide the estimated time when each customer can be seated at their table, allowing them to indulge in the delicious hot pot experience.
Please take a look at the following GIF demonstration for a better understanding of the sample I/O.
Input
The first line contains two integers N and M - the number of guests and the number of table types.
For each of the next N lines, the i-th line represents the i-th guest arrival at the restaurant. It’s given in the following format:
<arrival timestamp> <group size> <dining duration>
We use an integer to represent the timestamp. The timestamp of a guest being seated at a table plus their dining duration will determine when the table becomes available again.
Each of the next M lines represents the number of the tables for each size in the restaurant. It’s given in the following format:
<table size> <number of tables>
Output
Output N lines, where the i-th line shows the timestamp when the i-th guest can have their table.
Constraints
- 1 ≤ N ≤ 200000, 1 ≤ M ≤ 2
- Guests
- 0 ≤
arrival timestamp≤ 109 (The given arrival time is in increasing order) - 1 ≤
group size≤ max(table size) - 1 ≤
dining duration≤ 120
- 0 ≤
- Tables
- 1 ≤
table size≤ 6 - 1 ≤
number of tables≤ 50
- 1 ≤
- It's guaranteed that the answer will not exceed 109