2650. Gear Factory

单点时限: 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.

  • Each gear has a simple ratio and does not have a ratio of 1 to 1.
  • Any ratio can be made by only one combination of the gears or cannot.
  • The number of each ratio gear is limitless.

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.

样例

Input
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
Output
1 -2
impossible
-1 -1 1
2 0

0 人解决,2 人已尝试。

0 份提交通过,共有 2 份提交。

9.9 EMB 奖励。

创建: 15 年,2 月前.

修改: 7 年,2 月前.

最后提交: 1 月,2 周前.

来源: The 1st Imos Contest

题目标签