Достопримечательности
Как студент факультета компьютерных наук, вы, конечно, обожаете проводить время на свежем воздухе, поэтому решили отправиться в поход. В этом году вы выбрали для отпуска остров, полный живописных мест. Вы уже наметили несколько многообещающих маршрутов, но столкнулись с некоторыми трудностями. Количество возможных вариантов настолько велико, что вы решили выбрать лишь "небольшое" подмножество, состоящее не более чем из 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, которые описывают маршрут (в порядке важности). c_p указывает длину маршрута в минутах. c_xy указывает время в пути от официального начала или конца маршрута до начала или конца следующего по важности маршрута, где x и y могут быть либо b, либо e. Все указанные значения — неотрицательные целые числа, не превышающие 10^6. Поскольку вам нужно вернуться к своей машине, список является циклическим. Кроме того, мы будем игнорировать время, которое требуется, чтобы добраться до начала вашего путешествия на машине.
Выходные данные
Для каждого теста выведите одну строку. Вывод должен содержать список из F или B для каждого маршрута (в порядке), указывающий, нужно ли пройти маршрут в прямом направлении или в обратном. Если вы не можете совершить полную поездку в течение запланированного времени T, вы должны вывести IMPOSSIBLE, чтобы указать, что эти поездки — это слишком много походов. Вы можете предположить, что оптимальное решение всегда уникально.