Mars Jumper is a new improved model of Moon Rover. Clever heads from the engineering department
proved that in the conditions of low gravity it's easier to jump, so the new vehicle moves by jumping. By
the way, the length of its jump is always one meter. Mars Jumper is controlled with a standard computer
keyboard. To assign the direction of jumping, one uses the complementary digit keys (those which are
on the right). It is very convenient and handy: 8 means a jump northward, 2 means a jump southward,
6 means a jump eastward, 7 means a jump to the north-west, and so on. 5 is an order to take a sample
of soil. In order to use the zero key, the chief engineer invented one more function: if this key is pressed,
the motor of the vehicle is self-destroyed. He thinks that this function could be very useful.
Of course, to operate the Jumper is not an easy task. Not anyone can quickly move the vehicle, for
example, half a meter to the north. According to the designers, Mars Jumper can jump to a position
arbitrarily close to any specied point by means of a finite number of jumps.
The customers agreed to pay for the design and manufacture of Mars Jumper only after a trial. To conduct
a trial, the chief engineer seated his daughter at a computer and oered her to press some buttons. The
result of the trial was that the Jumper had jumped away. Now the engineers need to find it urgently.
Your task is to tell the search team where to find the Jumper. You know that the vehicle stopped at
the moment when the zero key was first pressed, or, if this key was not pressed, at the end of the route
determined by the sequence of pressed keys. You are given this sequence. You must determine the final
position of Mars Jumper. The testing area is considered to be an innite plane.
Not more than 106 digits from 0 to 9.
You should output the final coordinates of Mars Jumper (in meters, with absolute or relative error
not exceeding 10−10) in
the form X Y, where X is the displacement of the Jumper from the initial point to the east and Y is its
displacement to the north.
Problem Author: Stanislav Vasilyev
Problem Source: The Ural State University Championship, October 29, 2005