Cho mảng ~A~ gồm ~m~ phần tử (các phần tử được đánh số từ 1 đến ~m~) và mảng ~B~ gồm ~n~ phần tử (các phần tử được đánh số từ 1 đến ~n~), mỗi phần tử của hai mảng chỉ nhận một trong ba giá trị -1, 0, 1. Tiến hành tạo bảng ~C~ kích thước ~m \times n~, trong đó phần tử ~(i, j)~ nhận giá trị ~C[i][j] = A[i] \times B[j]~ với ~1 \le i \le m~ và ~1 \le j \le n~.

Một bảng con vuông kích thước ~s~ của bảng ~C~ có phần tử trái trên là ~(x, y)~ và phần tử phải dưới là ~(x + s - 1, y + s - 1)~ với ~1 \le x \le m - s + 1~ và ~1 \le y \le n - s + 1~ được gọi là bảng con vuông "cân bằng" nếu: 1) Các phần tử thuộc đường chéo chính đều nhận giá trị bằng 1. Cụ thể, các phần tử ~(x, y), (x+1, y+1), ..., (x+s-1, y+s-1)~ có giá trị bằng 1. 2) Tổng tất cả các phần tử trong bảng con vuông bằng 0.

Yêu cầu: Cho hai mảng ~A~ và ~B~, đếm số bảng con vuông "cân bằng" trong bảng ~C~.

Input

• Dòng đầu chứa hai số nguyên dương ~m, n~;
• Dòng thứ hai gồm ~m~ số mô tả mảng ~A~;
• Dòng thứ ba gồm ~n~ số mô tả mảng ~B~.

Output

• Ghi ra thiết bị ra chuẩn một số là số bảng con vuông "cân bằng" trong bảng ~C~.

Sample Input 1

3 4
1 -1 1
1 0 -1 1

Sample Output 1

1

Giải thích: Bảng ~C~: | B\A | 1 | -1 | 1 | |---|---|---|---| | 1 | 1 | -1 | 1 | | 0 | 0 | 0 | 0 | | -1 | -1 | 1 | -1 | | 1 | 1 | -1 | 1 |

Chỉ có duy nhất một bảng con vuông "cân bằng" là bảng con kích thước 2 có phần tử trái trên là (2, 3). (Wait, the explanation says (2,3), let me double check the matrix orientation in the PDF). In the PDF image, the rows are from $A$ and columns from $B$, or vice-versa? The image shows rows correspond to $A$ and columns to $B$. So $C[i][j] = A[i] \times B[j]$. Wait, the sample explanation says "phần tử trái trên là (2,3)". If $A = [1, -1, 1]$ and $B = [1, 0, -1, 1]$. $C$: Row 1 (A=1): 1, 0, -1, 1 Row 2 (A=-1): -1, 0, 1, -1 Row 3 (A=1): 1, 0, -1, 1 Submatrix size 2 starting at (2, 3): $C[2][3] = A[2] \times B[3] = (-1) \times (-1) = 1$ $C[3][4] = A[3] \times B[4] = 1 \times 1 = 1$ Diagonal: $C[2][3]=1, C[3][4]=1$. Correct. Sum: $C[2][3] + C[2][4] + C[3][3] + C[3][4] = 1 + (-1) + (-1) + 1 = 0$. Correct.

Subtasks

• Subtask 1 (20 điểm): ~m, n \le 30~;
• Subtask 2 (20 đ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 \cdot 10^6~.