Bảng số

Trong kỳ huấn luyện UIT Algo Bootcamp, các trại sinh sẽ được thử thách với những bài toán đa dạng nhằm nâng cao kỹ năng giải thuật, chuẩn bị cho đấu trường ICPC. Một trong những bài tập đầu tiên liên quan đến ma trận, một chủ đề quan trọng trong nhiều kỳ thi lập trình.

Giảng viên đưa ra hai dãy số \(A\) và \(B\). Dãy \(A\) gồm \(m\) phần tử, và dãy \(B\) gồm \(n\) phần tử. Mỗi phần tử trong hai dãy này chỉ có thể nhận một trong ba giá trị: \(-1, 0, 1\). Từ hai dãy này, các bạn sẽ tạo ra một ma trận \(C\) có kích thước \(m \times n\), với mỗi phần tử tại vị trí \((i, j)\) được tính bằng công thức: \(C[i][j] = A[i] \times B[j]\).

Để đánh giá khả năng xử lý dữ liệu và tìm kiếm mô hình của các trại sinh, một khái niệm mới được giới thiệu: "ma trận con vuông cân bằng". Một ma trận con vuông kích thước \(s\) của ma trận \(C\) được coi là "cân bằng" nếu nó thỏa mãn hai điều kiện sau:

• Các phần tử trên đường chéo chính của ma trận con đều bằng \(1\).
• Tổng tất cả các phần tử trong ma trận con đó bằng \(0\).

Yêu cầu: Cho hai dãy số \(A\) và \(B\), hãy đếm tổng số ma trận con vuông "cân bằng" có thể tìm thấy trong ma trận \(C\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(m\) và \(n\).
• Dòng thứ hai chứa \(m\) số nguyên mô tả dãy \(A\).
• Dòng thứ ba chứa \(n\) số nguyên mô tả dãy \(B\).

Output

• In ra một dòng duy nhất chứa một số nguyên là tổng số ma trận con vuông "cân bằng".

Example

3 4
1 -1 1
1 0 -1 1

1

Scoring

• Subtask 1 (20 điểm): \(m, n \le 30\).
• Subtask 2 (30 điểm): \(m, n \le 300\).
• Subtask 3 (30 điểm): \(m, n \le 1000\).
• Subtask 4 (20 điểm): \(m \times n \le 5 \times 10^6\).