Bessie is learning how to control a robot she has recently received as a gift.
The robot begins at point (0,0) on the coordinate plane and Bessie wants the robot to end at point (xg,yg). Bessie initially has a list of N (1≤N≤40) instructions to give to the robot, the i-th of which will move the robot xi units right and yi units up (or left or down when xi and yi are negative, respectively).
For each K from 1 to N, help Bessie count the number of ways she can select K instructions from the original N such that after the K instructions are executed, the robot will end at point (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 N. The next line contains xg and yg, each in the range −10^9…10^9. The final N lines describe the instructions. Each line has two integers xi and yi, also in the range −10^9…10^9.
It is guaranteed that (xg,yg)≠(0,0) and (xi,yi)≠(0,0) for all i.
OUTPUT FORMAT (print output to the terminal / stdout):
Print N lines, the number of ways Bessie can select K instructions from the original N for each K from 1 to N.
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≤20.
Test cases 5-16 satisfy no additional constraints.
Problem credits: Alex Liang