THỰC HÀNH

Cho một bảng vuông kích thước n × n, các dòng của bảng được đánh số từ 0 đến n - 1, từ trên xuống dưới và các cột của bảng được đánh số từ 0 đến n - 1, từ trái qua phải. Ô nằm trên giao của dòng i và cột j được gọi là ô (i, j) và trên ô đó chứa giá trị là aij bằng 0 hoặc 1.

Bạn cần viết chương trình thực hiện các công việc sau:

• Đếm số lượng hình chữ nhật trong bảng thỏa mãn:
  • Hình chữ nhật chỉ bao gồm các phần tử số 0;
  • Các cạnh song song với các cạnh của bảng vuông ban đầu.
• Nhận vào  truy vấn dạng (u, v), sau mỗi truy vấn sẽ đổi giá trị a_uv từ 0 thành 1 hoặc từ 1 thành 0.
• Sau mỗi truy vấn, bạn hãy đếm lại số lượng hình chữ nhật trong bảng thỏa mãn:
  • Hình chữ nhật chỉ bao gồm các phần tử số 0;
  • Các cạnh song song với các cạnh của bảng vuông ban đầu

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên n, Q (1 ≤ n ≤ 1000, 0 ≤ Q ≤ 10000)
• Dòng tiếp theo, dòng thứ i chứa 1 xâu ký tự độ dài n chỉ gồm hai ký tự ‘0’ hoặc ‘1’ mô tả dòng thứ i của bảng vuông n × n
• Dòng tiếp theo, dòng thứ j ghi hai số nguyên u, v (0 ≤ u, v ≤ n - 1) mô tả truy vấn j.

Dữ liệu ra:

• Dòng 1: Số lượng hình chữ nhật thỏa mãn điều kiện đầu bài trên bảng ban đầu;
• Dòng tiếp theo, dòng thứ j ghi số lượng hình chữ nhật thỏa mãn điều kiện đầu bài sau truy vấn j.

Example

Input:
4 3
0001
0100
1000
0010
1 2
1 1
2 0

Output:
29
23
31
45

Giải thích:

Ban đầu: Có 12 - 1х1, 6 - 1х2 , 2 - 1х3, 6 - 2х1, 1 - 2х2, 2 - 3х1. Tổng 12+6+2+6+1+2 = 29

• Sau truy vấn 1:

0001
0110
1000
0010

Có 11 - 1х1, 5 - 1х2, 2 - 1х3, 4 - 2х1, 1 - 3х1. Tổng 11+5+2+4+1 = 23

• Sau truy vấn 2:

0001
0010
1000
0010

Có 12 - 1х1, 6 - 1х2, 2 - 1х3, 6 - 2х1, 1 - 2х2, 3 - 3х1, 1 – 4x1. Tổng 12+6+2+6+1+3+1 = 31

• Sau truy vấn 3:

0001
0010
0000
0010

Có 13 - 1х1, 7 - 1х2, 3 - 1х3, 1 - 1х4, 8 - 2х1, 3 - 2х2, 5 - 3х1, 2 – 3x2, 2 - 4х1, 1 – 4x2. Tổng 13+7+3+1+8+3+5+2+2+1 = 45

Ràng buộc:

Subtask 1 (20% số điểm): n ≤ 50, Q ≤ 10

Subtask 2 (15% số điểm): n ≤ 400, Q = 0;

Subtask 3 (25% số điểm): n ≤ 400, Q ≤ 1000;

Subtask 4 (20% số điểm): n ≤ 1000, Q = 0;

Subtask 5 (20% số điểm): n ≤ 1000, Q ≤ 10000.