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 (xg,yg**)(xg,yg). Bessie initially has a list of NN (1≤N≤40**1≤N≤40) instructions to give to the robot, the ii-th of which will move the robot xixi units right and yiyi units up (or left or down when xixi and yiyi 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 (xg,yg**)**(xg,yg).

Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN. The next line contains xgxg and ygyg, each in the range −109…109−109…109. The final NN lines describe the instructions. Each line has two integers xixi and yiyi, also in the range −109…109−109…109.It is guaranteed that (xg,yg**)≠(0,0)(xg,yg)≠(0,0) and (xi,yi)≠(0,0)**(xi,yi)≠(0,0) for all ii.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
2
0
3
0
1
0

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)

SCORING:

• Test cases 2-4 satisfy N≤20N≤20.
• Test cases 5-16 satisfy no additional constraints.