Bảng số

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),\dots ,(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$.

Dữ liệu vào

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

Dữ liệu ra

In ra một dòng chứa một số là số bảng con vuông "cân bằng" trong bảng $C$.

Ràng buộc

• $m,n\ge 1$; $m\times n\le 5\times {10}^6$;
• $A[i],B[j]\in \{-1,0,1\}$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $m,n\le 30$;
• Subtask 2 ($30\%$ số điểm): $m,n\le 300$;
• Subtask 3 ($30\%$ số điểm): $m,n\le 1000$;
• Subtask 4 ($20\%$ số điểm): $m\times n\le 5\times {10}^6$.

Ví dụ