#1254. CNTRECT - Đếm hình chữ nhật

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

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ố ;
  • 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 , sau mỗi truy vấn sẽ đổi giá trị từ thành hoặc từ thành .
• 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 như trên.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ;
• dòng tiếp theo, dòng thứ chứa xâu ký tự độ dài chỉ gồm hai ký tự hoặc mô tả dòng thứ của bảng vuông ;
• dòng tiếp theo, dòng thứ ghi hai số nguyên mô tả truy vấn .

Dữ liệu ra:

• Dòng đầu ghi 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ứ ghi số lượng hình chữ nhật thỏa mãn điều kiện đầu bài sau truy vấn .

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

29
23
31
45

Giải thích:

• Ban đầu có hình , hình , hình , hình , hình , và hình . Tổng hình.
• Truy vấn :

0001
0110
1000
0010

Có hình , hình , hình , hình , và hình . Tổng hình.

• Truy vấn :

0001
0010
1000
0010

Có hình , hình , hình , hình , hình , hình , và hình . Tổng hình.

• Truy vấn 3

0001
0010
0000
0010

Có hình , hình , hình , hình , hình , hình , hình , hình , hình , hình . Tổng hình.

Ràng buộc:

• Subtask # ( số điểm): ;
• Subtask # ( số điểm): ;
• Subtask # ( số điểm): ;
• Subtask # ( số điểm): ;
• Subtask # ( số điểm): .