SP9124 GCPC11H - Sightseeing

As a computer science student you are of course very outdoorsie, so you decided to go hiking. For your vacation this year, you located an island full of nice places to visit. You already identified a number of very promising tracks, but are still left with some problems. The number of choices is so overwhelming, that you had to select only a "small" subset of at most _10 $ ^{5} $_ sights. And if that is not enough, you are very picky about the order in which you want to visit the sights. So you have already decided on an order in which you want to visit the preselected tracks. The problem you are left with is to decide in which direction to travel along each single track, and whether you may have to reduce your choice of tracks even further. After identifying the travel time between the endpoints of different tracks, you decide to write a program to figure out if you can make all your trips within the time you have planned for your vacation. Since you also do not want to waste any precious time, you only care about an optimal solution to your problem. Furthermore, the tracks can get pretty challenging. Thats why you do not want to hike along a track more than once.

The first line of the input gives the number of test cases _C_ (_0 < C ). The first line of each such test case holds two integers _N_, _T_ the number of tracks of the current hiker (_1 ) and the maximal time spent hiking throughout the vacation (_0 ). Each of the following _N_ lines holds five integers _c $ _{p} $_ , _c $ _{bb} $_ , _c $ _{be} $_ , _c $ _{eb} $_ and _c $ _{ee} $_ that describe a track (in order of importance). _c $ _{p} $_ gives the length of the track in minutes. _c $ _{xy} $_ gives the travel time of the official **b**egin or **e**nd of a track to the **b**eginning or **e**nd of the next most important track, where _x_ and _y_ are either _b_ or _e_. All values given are non-negative integers not greater than _10 $ ^{6} $_ . Since you have to get back to your car, the list is circular. Furthermore, we will ignore the time it takes you to get to the start of your trip with your car.___

For each test case print one line. The output should contain a list of either **F** or **B** for every track (in order) indicating whether you have to hike the track in forward direction or backward direction. If you cannot make the full trip within the planned time _T_, you should print **IMPOSSIBLE** to indicate that these trips are just too much hiking. You can assume that the optimal solution is always unique.