Trong trò chơi này, có một bảng màu có kích thước ~m \times n~, mỗi ô được tô một màu, các ô khác nhau có thể có màu giống nhau.

Yêu cầu: Với hai số nguyên ~H~ và ~W~, nhiệm vụ của 2 bạn là đếm số bảng màu con của bảng màu trên có kích thước ~H \times W~ (gồm ~H~ hàng liên tiếp và ~W~ cột liên tiếp) thỏa mãn: không có màu nào xuất hiện nhiều hơn một nửa số lượng ô của bảng màu con đó, tức là mỗi màu xuất hiện không quá ~H \cdot W / 2~ lần trong bảng màu con.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~m, n~ (~1 \le n \times m \le 10^6~);
• Dòng thứ hai chứa hai số nguyên dương ~H, W~ (~H \le m~, ~W \le n~);
• ~m~ dòng sau, dòng thứ ~i~ chứa ~n~ số nguyên dương ~a_{i,1}, a_{i,2}, \dots, a_{i,n}~ là mã màu của ~n~ ô tương ứng trên hàng ~i~ của bảng (~a_{i,j} \le 10^9~).

Kết quả

Một số là số bảng màu con thỏa mãn.

Ví dụ

Ví dụ 1

COUNT.INP

2 4
1 3
1 5 4 5
4 5 7 6

COUNT.OUT

3

Giải thích: Có 3 hình thỏa mãn là:

• Hình 1: 1 5 4
• Hình 2: 4 5 7
• Hình 3: 5 7 6

Ví dụ 2

COUNT.INP

4 3
2 3
2 6 2
2 4 2
6 5 1
1 2 3

COUNT.OUT

2

Giải thích: Có 2 hình thỏa mãn là:

Hình 1:

2 4 2
6 5 1

Hình 2:

6 5 1
1 2 3

Giới hạn

• 30% số test (30% số điểm): ~m \times n \le 1000~;
• 20% số test (20% số điểm): ~m = 1~, ~n < 10^6~;
• 30% số test (30% số điểm): ~m \times n \le 10^6~, ~|a_{i,j}| \le 5~ với mọi ~1 \le i \le m, 1 \le j \le n~;
• 20% số test còn lại không có ràng buộc gì thêm.