题目描述

贝茜正在学习如何控制她的机器人。

初始时，机器人位于 $(0,0)$ 处。

贝茜希望控制机器人行动至 $(X_g,Y_g)$。

贝茜有一个包含 $N$ 条指令的指令列表，其中第 $i$ 个指令命令机器人向右移动 $x_i$ 单位长度，并向上移动 $y_i$ 单位长度。

当 $x_i$ 为负时，表示机器人向左移动，同理，当 $y_i$为负时，表示机器人向下移动。

对于 $1∼N$ 中的每一个 $K$，贝茜想知道共有多少种从指令列表中选择 $K$ 个指令的选法，可以满足机器人在执行完这 $K$ 个指令后，能够成功行动至 $(X_g,Y_g)$ 处。

输入格式

第一行包含整数 $N$。

第二行包含两个整数$(X_g,Y_g)$。

接下来 $N$ 行，每行包含两个整数 $x_i,y_i$。

输出格式

共 $N$ 行，第 $i$ 行输出选择 $i$ 个指令执行并成功抵达 $(X_g,Y_g)$ 的选法数量。

7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10

0
2
0
3
0
1
0

提示

$1≤N≤40,$
$−10^9≤X_g,Y_g,x_i,y_i≤10^9,$
$(X_g,Y_g)≠(0,0),$
$(x_i,y_i)≠(0,0)。$

样例解释

在此样例中，贝茜共有 6 种满足条件的选择指令的选法：

(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (选择第 1、2、3、5、6、7 个指令)
(-2,0) (3,0) (4,0) (0,10) (选择第 1、2、3、5 个指令)
(-2,0) (3,0) (4,0) (0,10) (选择第 1、2、3、7 个指令)
(5,0) (0,10) (0,-10) (0,10) (选择第 4、5、6、7 个指令)
(5,0) (0,10) (选择第 4、5 个指令)
(5,0) (0,10) (选择第 4、7 个指令)