Robot Instructions

문제

Bessie is learning how to control a robot she has recently received as a gift.

The robot begins at point $(0,0)(0,\; 0)$ on the coordinate plane and Bessie wants the robot to end at point $(x_g,y_g)(x\_g,\; y\_g)$. Bessie initially has a list of $NN$ ($1\le N\le 401\backslash le\; N\backslash le\; 40$) instructions to give to the robot, the $ii$-th of which will move the robot $x_{i}x\_i$ units right and $y_{i}y\_i$ units up (or left or down when $x_{i}x\_i$ and $y_{i}y\_i$ are negative, respectively).

For each $KK$ from $11$ to $NN$, help Bessie count the number of ways she can select $KK$ instructions from the original $NN$ such that after the $KK$ instructions are executed, the robot will end at point $(x_g,y_g)(x\_g,\; y\_g)$.

입력

The first line contains $NN$. The next line contains $x_{g}x\_g$ and $y_{g}y\_g$, each in the range $-{10}^9\dots {10}^9-10^9\; \backslash ldots\; 10^9$. The final $NN$ lines describe the instructions. Each line has two integers $x_{i}x\_i$ and $y_{i}y\_i$, also in the range $-{10}^9\dots {10}^9-10^9\; \backslash ldots\; 10^9$.

It is guaranteed that $(x_g,y_g)\mathrm{\ne }(0,0)(x\_g,y\_g)\backslash neq\; (0,0)$ and $(x_i,y_i)\mathrm{\ne }(0,0)(x\_i,y\_i)\backslash neq\; (0,0)$ for all $ii$.

출력

Print $NN$ lines, the number of ways Bessie can select $KK$ instructions from the original $NN$ for each $KK$ from $11$ to $NN$.

힌트

In this example, there are six ways Bessie can select the instructions:

(-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)

For the first way, the robot's path looks as follows:

(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)

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

0
2
0
3
0
1
0