Беси учится управлять роботом, который она недавно получила в подарок.
Робот начинает в точке \((0, 0)\) координатной плоскости и Беси хочет
привести робота в точку \((x_g, y_g)\). Изначально у Беси есть список из \(N\)
(\(1\le N\le 40\)) инструкций для робота, \(i\)-ая из которых перемещает робота на
\(x_i\) единиц вправо и на \(y_i\) единиц вверх (или влево и вниз, если
\(x_i\) и \(y_i\) отрицательные, соответственно).
Для каждого \(K\) от \(1\) to \(N\), вычислите количество способов, которыми Беси
может выбрать \(K\) инструкций из исходного списка так, что после применения
этих \(K\) инструкций, робот окажется в точке \((x_g, y_g)\).
**Замечание: лимиты на время и память в этой задаче увеличены вдвое
до 4s и 512MB, относительно значений по умолчанию.**
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\). Следующая строка содержит
\(x_g\) и
\(y_g\),
каждое в интервале
\(-10^9 \ldots 10^9\). Последующие
\(N\) описывают инструкции.
Каждая строка содержит два целых числа
\(x_i\) и
\(y_i\), также в интервале
\(-10^9 \ldots 10^9\).
Гарантируется, что \((x_g,y_g)\neq (0,0)\) и \((x_i,y_i)\neq (0,0)\) для всех
\(i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(N\) строк, количество способов, которыми Беси может выбрать \(K\)
инструкций из списка оригинальных \(N\), для каждого \(K\) от \(1\) до \(N\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10
|
0
2
0
3
0
1
0
|