As director of the Causality Infraction Agency, your primary objective is track down and arrest unscrupulous individuals attempting to alter the course of history.
Although your mission briefings include the exact year that a time agent must travel to, the physics of time travel don't make it quite so simple. Time travel can only be done by moving through wormholes that connect two specific instances of time together. As a result, an agent must travel through several wormholes in sequence to reach his or her destination time. In addition, an agent may have to spend some time living in the past or future while waiting for the next wormhole to appear. Traveling through a wormhole also isn't as simple as it might seem: moving forward in time through a wormhole will instanteously age the user by a certain number of years and moving backwards through one will instanteously make the traveller slightly younger.
Because the agency pays its agents based on how many years they've aged since joining the service, you are required to minimize the "aging process" as much as possible for every agent. Your goal therefore is to write a program that finds the optimal itinerary of wormhole jumps for each agent's mission and then reports the total number of years each agent will age after completing their assignment.
For agency accounting purposes, the formulas for computing total years aged on a mission are as follows:
destination - origin
In other words, if you were currently in the year 1785 and had to wait until the year 1793, then you will have aged 8 years.
floor((arrival - departure) / 2)
Put in another way, you will age half the number of years (rounded down) you normally would have had you instead waited for the equivalent number of years to pass by. Note that when traveling over a small enough time difference, the years aged may be rounded down to zero for accounting purposes.
floor((departure - arrival) / 4)In other words, you gain back a quarter of the difference between the two years (rounded down). Note that when traveling over a small enough time difference, the years "gained back" may be rounded down to zero for accounting purposes.
Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:
For each data set in the input, output the heading "DATA SET #k" where k is 1 for the first data set, 2 for the second, and so on. Then print M lines showing the results of each of the M missions from the input and in the same relative order as the input. Each of the M lines should contain either a single integer indicating the number of years aged by that respective agent or the words "IMPOSSIBLE" if that particular mission cannot be completed (either because the destination is unreachable or a return trip is not possible).
1 2 2011 1956 1975 2005 2008 3 1969 2012 1982
DATA SET #1 27 IMPOSSIBLE 42