0 人解决,2 人已尝试。
0 份提交通过,共有 2 份提交。
9.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
Imo Company has a gear factory. As the factory has some ratio gears, various ratio gears are provided by the combination of those gears. Having 2:1 and 3:1 gears, it may provide 4:9 gear with two 2:1 ones and two 3:1 ones. The provision is very reasonable for lower costs because it is easy to produce the certain ratio gears. Of course, some ratio gears cannot be produced for its combination of gears in possession.
Recently the factory is receiving many orders. But some of the orders are not excutable for the lack of available gears. For lower expenditure, you must make a program to judge whether the factory can produce and to tell how to satisfy the requests.
The gears which it has satisfy the following conditions.
The set of gears– 3:2, 2:1, 3:1 –does not satisfy the second of the above conditions because 3:2 can be made by two ways. One 2:1 and one 3:1 (if you turn 2:1 and connect two gears, 3:2 can be made 1 : 2 × 3 : 1 = 3 : 2) produce 3:2, and of course 3:2 also produce 3:2 as is.
The input consists of multiple datasets, each of which contains integers and describes the list of the gears that the factory has, in the following format.
n x y
a1 b1
…
…
an bn
n (0 < n < 100) is the number of sorts of the gears that the factory has and x, y (0 < x, y < 100, 000) is an ordered gear whose ratio is x : y. And each of n lines following the first line contains a pair of integers ai and bi. Each set of ai (0 < ai < 100, 000) and bi (0 < bi < 100, 000) describes a gear whose ratio is ai : bi, that the factory has.
For each dataset, output a single line containing n integers delimited by single spaces or impossible.If the order can be produced, print n integers that represent the number of the gears to be used for the order. Otherwise print impossible. Output lines must not contain other characters.
The output must be written to standard output.
2 2 9 2 1 3 1 2 2 3 2 1 5 1 3 21 10 2 5 5 6 7 10 2 1 4 1 2 1 3 0 0 0
1 -2 impossible -1 -1 1 2 0
0 人解决,2 人已尝试。
0 份提交通过,共有 2 份提交。
9.9 EMB 奖励。