Robot Instruction Subset Sum

Bessie is learning how to control a robot she recently received as a gift. The robot starts at \((0,0)\) on the coordinate plane, and Bessie wants the robot to finish at \((x_g,y_g)\). She has a list of \(N\) instructions (where \(1 \le N \le 40\)). The \(i\)-th instruction moves the robot by \(x_i\) units in the horizontal direction and by \(y_i\) units in the vertical direction (note that a negative value indicates movement in the opposite direction).

For each \(K\) from 1 to \(N\), count the number of ways to select exactly \(K\) instructions (in any order) from the original list such that when executed, the robot reaches the target point \((x_g,y_g)\).

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

inputFormat

The first line contains three integers: \(N\), \(x_g\) and \(y_g\).

The following \(N\) lines each contain two integers \(x_i\) and \(y_i\), representing the \(i\)-th instruction.

outputFormat

Output \(N\) space‐separated integers. The \(K\)-th integer should be the number of ways to choose exactly \(K\) instructions that will move the robot from \((0,0)\) to \((x_g,y_g)\).

sample

3 1 1
1 0
0 1
1 1

1 1 0