The “cows” are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation onthe sunny shores of Lake Superior. Bessie, ever the competent travel agent, hasnamed the Bullmoose Hotel on famed <st1:street w:st="on"><st1:address w:st="on">Cumberland Street</st1:address></st1:street> as theirvacation residence. This immense hotel has N (1 <= N <= 50,000) rooms alllocated on the same side of an extremely long hallway (all the better to seethe lake, of course).
The “cows” and other visitors arrive in groups of size D_i (1 <= D_i <= N) andapproach the front desk to check in. Each group i requests a set of D_icontiguous rooms from Canmuu, the moose staffing the counter. He assigns them some set of consecutive roomnumbers r..r+D_i-1 if they are availableor, if no contiguous set of rooms is available, politely suggests alternate lodging. Canmuu always chooses the value of r to be thesmallest possible.
Visitors also depart the hotel fromgroups of contiguous rooms. Checkout i has the parameters X_i and D_i whichspecify the vacating of rooms X_i…X_i+D_i-1 (1 <= X_i <= N-D_i+1).Some (or all) of those rooms might be empty before the checkout.
Your job is to assist Canmuu byprocessing M (1 <= M < 50,000) checkin/checkout requests. The hotel isinitially unoccupied.<o:p></o:p>