Bảng rỗng

Trong một vương quốc xa xưa, có một khu rừng ma thuật được chia thành \(n \times n\) ô vuông, mỗi ô vuông có thể chứa đá quý (\(1\)) hoặc trống rỗng (\(0\)). Nhiệm vụ của các pháp sư trong vương quốc là đếm số lượng hình chữ nhật con, với các cạnh song song với cạnh của khu rừng, chỉ chứa các ô rỗng (các ô vuông chứa \(0\)).

Để làm cho nhiệm vụ thêm phần thú vị, các pháp sư được yêu cầu cập nhật các thay đổi trạng thái của một ô vuông từ rỗng (\(0\)) thành chứa đá quý (\(1\)) hoặc ngược lại. Sau mỗi thay đổi, họ lại phải đếm lại số lượng hình chữ nhật con thỏa mãn yêu cầu.

Nhận thấy đây là một bài toán quá hóc búa, các pháp sư chỉ còn có thể trông cậy vào bạn.
Lưu ý: các cập nhật sẽ thật sự thay đổi giá trị của một ô và có ảnh hưởng về sau.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 5000)\), lần lượt là kích thước bảng và số lượng truy vấn.
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi ký tự \(0\) và \(1\) độ dài \(n\), mô tả trạng thái ban đầu của khu rừng.
• \(q\) dòng cuối, mỗi dòng chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq n)\), mô tả tọa độ của ô vuông thay đổi trạng thái trong truy vấn thứ \(i\).

Output

In ra \(q + 1\) dòng:

• Dòng đầu tiên là số lượng hình chữ nhật con chỉ chứa các ô trống rỗng (\(0\)) trong trạng thái ban đầu của khu rừng.
• Mỗi dòng trong \(q\) dòng tiếp theo ghi số lượng hình chữ nhật thỏa mãn yêu cầu sau mỗi lần thay đổi trạng thái của ô vuông.

Example

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

29
23
31
45

Scoring

• Có \(20\%\) số test ứng với \(n, q \leq 50\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 150\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 400\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 1000\).
• Có \(20\%\) số test khác ứng với \(n, q \leq 5000\).