Огляд визначних пам'яток
Як студент комп'ютерних наук, ви, безсумнівно, любите проводити час на свіжому повітрі, тому вирішили вирушити в похід. Цього року ви знайшли острів, сповнений чудових місць для відвідування. Ви вже визначили кілька перспективних маршрутів, але все ще стикаєтеся з деякими проблемами. Кількість варіантів настільки велика, що вам довелося обрати лише "невелику" підмножину з не більше ніж 10^5 пам'яток.
І якщо цього недостатньо, ви дуже вибагливі щодо порядку, в якому хочете відвідувати пам'ятки. Тож ви вже вирішили, в якому порядку хочете відвідати попередньо обрані маршрути. Проблема, яка залишилася, полягає в тому, щоб визначити, в якому напрямку подорожувати кожним окремим маршрутом, і чи потрібно ще більше скоротити свій вибір маршрутів. Після визначення часу подорожі між кінцевими точками різних маршрутів, ви вирішили написати програму, щоб з'ясувати, чи зможете ви здійснити всі свої поїздки в межах часу, який ви запланували для своєї відпустки. Оскільки ви також не хочете витрачати дорогоцінний час, вас цікавить лише оптимальне рішення вашої проблеми. Крім того, маршрути можуть бути досить складними. Ось чому ви не хочете проходити маршрут більше одного разу.
Вхідні дані
Перший рядок вхідних даних задає кількість тестових випадків C (0 < C ≤ 100). Перший рядок кожного такого тестового випадку містить два цілі числа N, T — кількість маршрутів поточного туриста (1 ≤ N ≤ 10^5) та максимальний час, витрачений на похід протягом відпустки (0 ≤ T ≤ 10^6). Кожен з наступних N рядків містить п'ять цілих чисел c_p, c_bb, c_be, c_eb та c_ee, які описують маршрут (в порядку важливості). cp задає довжину маршруту в хвилинах. c_xy задає час подорожі від офіційного початку або кінця маршруту до початку або кінця наступного за важливістю маршруту, де x та y можуть бути або b, або e. Усі значення, що надані, є невід'ємними цілими числами, не більшими за 10^6. Оскільки вам потрібно повернутися до своєї машини, список є циклічним. Крім того, ми ігноруємо час, який вам потрібно, щоб дістатися до початку своєї поїздки на машині.
Вихідні дані
Для кожного тестового випадку виведіть один рядок. Вихідні дані повинні містити список з F або B для кожного маршруту (в порядку), що вказує, чи потрібно йти маршрутом у прямому напрямку або у зворотному напрямку. Якщо ви не можете здійснити повну поїздку в межах запланованого часу T, ви повинні вивести IMPOSSIBLE, щоб вказати, що ці поїздки — це занадто багато походів. Ви можете припустити, що оптимальне рішення завжди є унікальним.