SCUSA Region ACM Balloon Logo ICPC Masthead
2008 ACM ICPC South Central USA Regional Programming Contest

No Wormholes Were Harmed...

Introduction:

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:

Each dataset to this problem will contain a starting year from which all agents begin their travels and a list of mission assignments, one for each agent. Every mission assignment includes a final destination year that the agent must travel to. The mission can only be completed if the agent is able to make a round trip by traveling from the starting year to the mission's destination year and then traveling back to the initial starting year again. If such a round trip cannot be completed, then that particular mission is invalid. For the purposes of this problem, you also do not have to consider the maximum lifespan of any given agent. A mission is considered valid as long as a round trip is possible regardless of how high the count of years aged will be.

Input:

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:

Output:

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).

Sample Input:

1
2
2011 1956
1975 2005
2008
3
1969
2012
1982

Sample Output:

DATA SET #1
27
IMPOSSIBLE
42