Gəzinti#6550
Bir kompüter elmləri tələbəsi olaraq, açıq havada çox vaxt keçirdiyiniz üçün yürüyüşə çıxmağa qərar verdiniz. Bu ilki tətiliniz üçün ziyarət etmək üçün gözəl yerlərlə dolu bir ada tapdınız. Artıq bir sıra çox ümidverici yollar müəyyən etmisiniz, lakin hələ də bəzi problemlərlə üzləşirsiniz. Seçimlərin sayı o qədər böyükdür ki, yalnız maksimum 10^5 görməli yerlərin "kiçik" bir alt qrupunu seçməli oldunuz.
Və bu kifayət deyilsə, görməli yerləri hansı ardıcıllıqla ziyarət etmək istədiyinizə çox diqqətlisiniz. Beləliklə, əvvəlcədən seçilmiş yolları hansı ardıcıllıqla ziyarət etmək istədiyinizə artıq qərar vermisiniz. Qarşılaşdığınız problem hər bir yolu hansı istiqamətdə keçəcəyinizə və hətta yol seçiminizi daha da azaltmalı olub-olmadığınıza qərar verməkdir. Müxtəlif yolların son nöqtələri arasındakı səyahət vaxtını müəyyən etdikdən sonra, tətiliniz üçün planlaşdırdığınız vaxt ərzində bütün səyahətlərinizi həyata keçirə biləcəyinizi öyrənmək üçün bir proqram yazmağa qərar verdiniz. Çünki siz də qiymətli vaxtınızı itirmək istəmirsiniz, probleminizin optimal həlli ilə maraqlanırsınız. Üstəlik, yollar olduqca çətin ola bilər. Buna görə də bir yolu bir dəfədən çox yürümək istəmirsiniz.
Girişin ilk sətri test hallarının sayını C (0 < C ≤ 100) verir. Hər bir belə test halının ilk sətri cari yürüyüşçünün yollarının sayını N (1 ≤ N ≤ 10^5) və tətil boyunca yürüyüşə sərf olunan maksimal vaxtı T (0 ≤ T ≤ 10^6) saxlayır. Növbəti N sətrin hər biri bir yolu təsvir edən beş tam ədəd c_p, c_bb, c_be, c_eb və c_ee saxlayır (əhəmiyyət sırasına görə). cp yolun dəqiqələrlə uzunluğunu verir. c_xy bir yolun rəsmi başlanğıc və ya sonundan növbəti ən vacib yolun başlanğıc və ya sonuna qədər olan səyahət vaxtını verir, burada x və y ya b, ya da e olur. Verilən bütün dəyərlər 10^6-dan böyük olmayan qeyri-mənfi tam ədədlərdir. Avtomobilinizə qayıtmalı olduğunuz üçün siyahı dövridir. Üstəlik, avtomobilinizlə səyahətinizin başlanğıcına çatmaq üçün lazım olan vaxtı nəzərə almayacağıq.
Hər bir test halı üçün bir sətir çap edin. Çıxış hər bir yol üçün (ardıcıllıqla) yolu irəli istiqamətdə və ya geri istiqamətdə keçməli olduğunuzu göstərən F və ya B siyahısını ehtiva etməlidir. Əgər planlaşdırılan vaxt T ərzində tam səyahəti həyata keçirə bilmirsinizsə, bu səyahətlərin çox yürüyüş olduğunu göstərmək üçün IMPOSSIBLE çap etməlisiniz. Optimal həllin həmişə unikal olduğunu fərz edə bilərsiniz.
Nümunə 1