Cô Thái rất thích sự tròn trĩnh của những chữ số \(0\). Là giáo viên chuyên tin, cô Thái cho các bạn học sinh giỏi làm bài tập đếm số lượng hình chữ nhật chỉ chứa toàn số \(0\) trong một bảng hình chữ nhật. Cụ thể, cho một bảng hình chữ nhật kích thước \(n \times n\) ô, mỗi ô chỉ chứa số \(0\) hoặc \(1\). Các hàng đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột đánh số từ \(1\) đến \(n\) từ trái qua phải. Có \(q\) truy vấn, mỗi truy vấn sẽ thay đổi giá trị của một ô từ \(0\) thành \(1\) hoặc từ \(1\) thành \(0\).

Yêu cầu: Với mỗi truy vấn, sau khi thay đổi giá trị hãy đếm số hình chữ nhật con (tính cả hình chữ nhật ban đầu) có cạnh song song với cạnh của bảng mà chỉ chứa các số \(0\).

Input

• Dòng đầu chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 5000\)).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa một xâu \(01\) độ dài \(n\) mô tả hàng thứ \(i\) của bảng ban đầu.
• Dòng thứ \(i\) trong số \(q\) dòng tiếp theo chứa hai số nguyên \(r, c\) (\(1 \le r, c \le n\)) mô tả tọa độ ô thay đổi giá trị trong truy vấn thứ \(i\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra gồm \(q + 1\) dòng trong đó:
  • Dòng đầu là số lượng hình chữ nhật con thỏa mãn của bảng ban đầu;
  • Mỗi dòng trong số \(q\) dòng tiếp theo ghi một số nguyên là kết quả của truy vấn tương ứng.

Example

4 3
0001
0100
1000
0010
2 3
2 2
3 1

29
23
31
45

Hạn chế

• Có \(20\%\) số test ứng với \(n, q \le 50\).
• Có \(20\%\) số test khác ứng với \(n, q \le 150\).
• Có \(20\%\) số test khác ứng với \(n, q \le 400\).
• Có \(20\%\) số test khác ứng với \(n, q \le 1000\).
• \(20\%\) số test còn lại không có giới hạn gì thêm.