Bugniverses are, excluding time, one-dimensional universes populated by dragonflys, grasshoppers and ants. Ants use dragonflys and grasshopers to travel (moving creates wormholes, so collisions are avoided). In each bugniverse there are two universal constants that determine the length of moves: grasshoppers always jump a meters and dragonflys always fly b meters (both moves either left or right).
The problem is, in some bugniverses not all traveling distances are possible. Suppose that an ant wants to travel from point A to point B, c meters apart (c can be positive or negative). If, for example, a=9, b=6 and the ant travels x=2 grasshoper moves (a× x = 18 meters) and y = −1 dragonfly moves (b× y = −6 meters), ends at c = 18 − 6 = 12 meters away from the start point. However, in that universe, it is impossible to travel c = 14 meters!
Given the bugniverse’s constants a,b and a travel distance c, the goal is to find out if either the travel is impossible and, if not, the travel solution: the minimum non-negative number of grasshopper moves, x, and the corresponding dragonfly moves, y, such that the travel ends c meters away from the start.
The first line of the input has a single integer, n, giving the number of travels to solve. Each one of next n lines contains three integers, a, b and c separated by single spaces, describing a travel problem. In each line, the first integer, a, is the length of grasshopper moves, b of dragonfly moves and c the travel distance.
The output has n lines. Each single line can be either the expression impossible, if the travel is impossible, or the two integers x and y, separated by a single space, with the travel solution. The first integer, x is the number of grasshoper moves and the second, y, the number of dragonfly moves.
|
3 5 3 -5 9 6 14 1043207 871185 2114708923
2 -5 impossible 255419 -303426
This document was translated from LATEX by HEVEA.