Trang trại của ông Per có một cái ao rất đẹp và rất to. Trong lúc đi thuyền trên ao, Per đã làm rơi mất chìa khóa nhà. Vì ao nuôi cá mập nên không thể xuống nước được, Per đành quay về và chế tạo một con robot biết lặn.

Bạn hãy coi mặt ao là mặt phẳng tọa độ ~Oxy~ vô hạn. Ban đầu robot ở tọa độ ~(0, 0)~; bằng máy dò, robot đã phát hiện chìa khóa nằm ở tọa độ ~(x_G, y_G)~.

Tuy nhiên, robot chỉ thực hiện được ~n~ thao tác đã được lập trình từ trước. Thực hiện thao tác thứ ~i~ thì robot sẽ di chuyển sang phải ~x_i~ đơn vị và lên trên ~y_i~ đơn vị (đi sang trái nếu ~x_i < 0~, đi xuống dưới nếu ~y_i < 0~). Mỗi thao tác chỉ được dùng nhiều nhất một lần, và thứ tự thực hiện không làm thay đổi vị trí cuối cùng của robot.

Với mỗi số ~k~ từ ~1~ tới ~n~, Per muốn biết có thể chọn ra ~k~ thao tác trong ~n~ thao tác ban đầu để robot tới được đúng chỗ chìa khóa hay không, và nếu được thì có bao nhiêu cách chọn.

Per đang lo lắng nên chẳng rõ kết quả. Các bạn học viên hãy thử giúp Per nhé!

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ — số thao tác của robot.
• Dòng thứ hai chứa hai số nguyên ~x_G~, ~y_G~ — tọa độ chìa khóa của Per.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x_i~, ~y_i~ — số đơn vị mà robot sẽ di chuyển nếu thực hiện thao tác thứ ~i~.

Dữ liệu luôn đảm bảo ~(x_G, y_G) \ne (0, 0)~ và ~(x_i, y_i) \ne (0, 0)~ với mọi ~i~.

Kết quả

Với mỗi ~k~ từ ~1~ tới ~n~ mà robot có thể tới được chỗ chìa khóa bằng đúng ~k~ thao tác, in ra trên một dòng hai số nguyên: ~k~ và số cách chọn ra ~k~ thao tác thỏa mãn. Các dòng được in theo thứ tự ~k~ tăng dần.

Nếu không có giá trị ~k~ nào thỏa mãn thì không in ra gì cả.

Ví dụ

Đầu vào:

6
6 8
2 4
4 4
2 -4
0 8
4 -8
2 8

Đầu ra:

2 1
3 3

Giải thích: Per có thể chọn như sau:

• ~(2, 4), (4, 4)~ (thao tác ~1, 2~);
• ~(2, 4), (2, -4), (2, 8)~ (thao tác ~1, 3, 6~);
• ~(4, 4), (2, -4), (0, 8)~ (thao tác ~2, 3, 4~);
• ~(0, 8), (4, -8), (2, 8)~ (thao tác ~4, 5, 6~).

Có ~1~ cách dùng ~2~ thao tác và ~3~ cách dùng ~3~ thao tác.

Giới hạn

• ~1 \le n \le 40~
• ~-10^9 \le x_i, y_i, x_G, y_G \le 10^9~

Với ~n = 40~ thì ~2^{40}~ tập con là quá nhiều. Hãy chia ~n~ thao tác thành hai nửa, liệt kê riêng từng nửa rồi ghép lại theo bộ ba (số thao tác đã dùng, tổng ~x~, tổng ~y~).