Robot Instructions

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 $(x_g, y_g)$. Bessie initially has a list of $N$ ($1\le N\le 40$) instructions to give to the robot, the $i$-th of which will move the robot $x_i$ units right and $y_i$ units up (or left or down when $x_i$ and $y_i$ 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 $(x_g, y_g)$.

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

The first line contains $N$. The next line contains $x_g$ and $y_g$, each in the range $-10^9 \ldots 10^9$. The final $N$ lines describe the instructions. Each line has two integers $x_i$ and $y_i$, also in the range $-10^9 \ldots 10^9$.

It is guaranteed that $(x_g,y_g)\neq (0,0)$ and $(x_i,y_i)\neq (0,0)$ for all $i$.

• Test cases 2-4 satisfy $N\le 20$.
• Test cases 5-16 satisfy no additional constraints.

Print $N$ lines, the number of ways Bessie can select $K$ instructions from the original $N$ for each $K$ from $1$ to $N$.

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

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