Bessie đang học cách điều khiển một rô-bốt mà cô mới được tặng.

Rô-bốt bắt đầu tại điểm \((0,0)\) trên mặt phẳng tọa độ và Bessie muốn nó kết thúc tại điểm \((x_g,y_g)\). Ban đầu Bessie có danh sách gồm \(N\) (\(1\le N\le 40\)) chỉ dẫn dành cho rô-bốt; chỉ dẫn thứ \(i\) sẽ di chuyển rô-bốt sang phải \(x_i\) đơn vị và lên trên \(y_i\) đơn vị (tương ứng là sang trái hoặc xuống dưới khi \(x_i\) hoặc \(y_i\) âm).

Với mỗi \(K\) từ \(1\) đến \(N\), hãy giúp Bessie đếm số cách chọn \(K\) chỉ dẫn trong \(N\) chỉ dẫn ban đầu sao cho sau khi thực hiện \(K\) chỉ dẫn đó, rô-bốt kết thúc tại điểm \((x_g,y_g)\).

Lưu ý: giới hạn thời gian và bộ nhớ của bài này lần lượt là 4 giây và 512 MB, gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng tiếp theo chứa \(x_g\) và \(y_g\), mỗi số nằm trong khoảng \(-10^9\ldots 10^9\). \(N\) dòng cuối mô tả các chỉ dẫn. Mỗi dòng có hai số nguyên \(x_i\) và \(y_i\), cũng nằm trong khoảng \(-10^9\ldots 10^9\).

Bảo đảm rằng \((x_g,y_g)\ne(0,0)\) và \((x_i,y_i)\ne(0,0)\) với mọi \(i\).

Dữ liệu ra

In \(N\) dòng; với mỗi \(K\) từ \(1\) đến \(N\), dòng thứ \(K\) là số cách Bessie có thể chọn \(K\) chỉ dẫn trong \(N\) chỉ dẫn ban đầu.

Phân nhóm

• Các test 2–4 thỏa mãn \(N\le 20\).
• Các test 5–16 không có ràng buộc bổ sung.

Ví dụ

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

0
2
0
3
0
1
0

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

Nguồn

USACO 2022 February Contest, Silver — Robot Instructions: https://usaco.org/index.php?page=viewproblem2&cpid=1207

Tác giả: Alex Liang.