2 Euclidean Adjustments

An astronomer is making measurements with his telescope when he notices that his vision field is off by x micronanometers (which we will assume is a measurement that exists) to the right. His telescope can only be moved to the right or to the left, however, and only via his automated, highly-calibrated machinery by certain predetermined fixed integer amounts. If, for example, one of these amounts is 7 micronanometers, then he can move his vision field by any multiple of 7 micronanometers to the left or right.

Given a value of x and a set {m₁,m₂,,m_n} of predetermined fixed movement amounts, your job will be to advise the astronomer as to which of the movements to choose, how many times the movement should be applied, and the direction of the movement so that he can make his field of vision perfect. You may assume that x is a standard Java integer, but you may want to use the java.BigInteger class for the m_i.

It is guaranteed that a solution exists.

3 Input/Output

The input file (input.txt) in the home directory will consist only of positive integers. The first line will be the value of x. The following lines will hold the values of the m_i, one per line.

Your output file (output.txt) should hold a sequence of lines with 2 singlespace-separated numbers per line. These will be interpreted as instructions for telescope movement. The line m_i y

will mean to move the telescope m_i micronanometers y times. (If y is positive, then it will be moved to the right; if y is negative, then it will be moved to the

left.)

1