404643: GYM101597 F Mattress Run

You are a big fan of a new hotel chain called Almost Complimentary Motels (ACM). You have recently noticed that this year this chain has launched a loyalty program for its most valuable customers. If you spend a certain number of nights or stays with the hotels from that chain, you will get "Diamond Spire" status with very valuable benefits, such as a guaranteed upgrade to the best room (known as "Billy's suite") on any stay.

In order to qualify for this status, you need to either accumulate 50 qualifying nights or 25 qualifying stays in a calendar year. Now, this year you are a little bit short on both of those criteria, and in order to meet them by the end of the year, you decide to make a mattress run. Around your town there are quite many hotels belonging to the ACM chain, most of them are pretty bad, and normally you wouldn't need to stay anywhere close to your home anyway. However in this case your plan is to make several reservations that will get you your status (by either stays or nights) that would cost you as little as possible.

Before you begin, there are several special rules from ACM chain that you need to know:

• You only collect qualifying nights and qualifying stays on special rates that may be unavailable some hotels on some check-in/check-out dates.
• Unlike many other chains, you may not make consecutive reservations in one hotel, i.e. the check out day for one reservation cannot coincide with the check in day for another reservation in the same hotel.
• Any two reservations should not overlap by nights, regardless of whether the hotel is the same.
• A stay with check-in day b and check-out day e gives you e - b qualifying nights credits and always 1 qualifying stay credit.

Find the strategy to qualify you with minimal total cost. If there are many possible strategies you may choose either of them.

On the first line you are given 3 integers: Y — the number of days remaining in the current year (2 ≤ Y ≤ 365), N — the number of nights required for qualification (1 ≤ N ≤ 50), S — the number of stays required for qualification (1 ≤ S ≤ 25).

The second line contains two integers: H — the number of hotels (1 ≤ H ≤ 50), M — the number of available rates (1 ≤ M ≤ 5000).

The next M lines describe all the available qualifying rates in the following way; each line contains 4 integers: h — the ID of the hotel (1 ≤ h ≤ H), b — the day of check-in, e — the day of check-out (1 ≤ b < e ≤ Y), c — the total cost of the stay on this rate (1 ≤ c ≤ 1000000).

If achieving the status is impossible, output a single line with the word "IMPOSSIBLE". Otherwise, output a mattress run with minimal possible cost. The first line should contain either "NIGHTS" or "STAYS", stating which qualification criteria you are intending to meet with your mattress run. The second line should contain one integer K — the number of bookings you are going to make. The third line should contain K 1-based indices (as they are listed in the input) of the fares you are planning to use for the bookings. Those fares should follow in the chronological order of their use.

5 3 2
2 5
1 1 2 5
1 2 3 4
1 1 3 20
1 3 5 15
2 3 4 10

STAYS
2
2 5 

5 3 3
1 4
1 1 2 5
1 2 3 5
1 3 4 5
1 4 5 5

IMPOSSIBLE