Lệnh Robot

Một robot bắt đầu tại tọa độ $(0,0)$ và cần đến đích $(x_g,y_g)$. Bessie có $N$ lệnh di chuyển, lệnh thứ $i$ sẽ di chuyển robot $x_i$ đơn vị sang phải và $y_i$ đơn vị lên trên (giá trị âm nghĩa là di chuyển sang trái hoặc xuống dưới).

Với mỗi $K$ từ $1$ đến $N$, đếm số cách chọn đúng $K$ lệnh trong $N$ lệnh sao cho khi thực hiện tất cả các lệnh được chọn (theo thứ tự bất kỳ), robot đến đúng đích.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• Dòng 2: Hai số nguyên $x_g,y_g$ — tọa độ đích
• $N$ dòng tiếp theo: Hai số nguyên $x_i,y_i$ — lệnh thứ $i$

Dữ liệu ra

• $N$ dòng, dòng thứ $K$ chứa số cách chọn đúng $K$ lệnh để robot đến đích.

Ràng buộc

• $1\le N\le 40$
• $-{10}^9\le x_g,y_g\le {10}^9$, $(x_g,y_g)\ne (0,0)$
• $-{10}^9\le x_i,y_i\le {10}^9$, $(x_i,y_i)\ne (0,0)$
• Giới hạn thời gian: 4 giây, bộ nhớ: 512MB

Ví dụ