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 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\) thỏa mãn có số ô có màu giống nhau trong bảng này, không có màu nào xuất hiện nhiều hơn một nửa số lượng các màu xuất hiện trong bảng đó.

Dữ liệu vào

• 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},...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)\).

Dữ liệu ra

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

Ràng buộc

• Có 30% số lượng test ứng với 30% số điểm thỏa mãn: \(m \times n \le 1000\).
• Có 20% số lượng test ứng với 20% số điểm thỏa mãn: \(m = 1, n \lt 10^6\).
• Có 30% số lượng test ứng với 30% số điểm thỏa mãn: \(m \times n \le 10^6, |a_{i,j}| \le 5, ∀: 1 \le i \le m, 1 \le j \le n\).
• 20% số lượng test còn lại không có ràng buộc gì thêm.

Input 1

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

Output 1

3

Input 2

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

Output 2

2