Бесі вчиться керувати роботом, який вона нещодавно отримала у подарунок.

Робот стартує в точці \((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, щодо значень за умовчанням.

Формат вхідних даних

Перший рядок містить \(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\).

Формат вихідних даних

Виведіть \(N\) рядків, кількість способів, якими Бесі може вибрати \(K\) інструкцій зі списку оригінальних \(N\), для кожного \(K\) від \(1\) до \(N\).

Приклад вхідних даних

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

Приклад вихідних даних

0
2
0
3
0
1
0

У цьому прикладі є 6 способів вибрати інструкції

(-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)

Для першого способу шлях робота виглядає так:

(0,0) -> (-2,0) -> (1,0) -> (5,0) -> (5,10) -> (5,0) -> (5,10)

ОЦІНЮВАННЯ:

• У тестах 2-4 \(N\le 20\).

• У тестах 5-16 немає додаткових обмежень. </ul>

  Автор: Alex Liang