You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1739 题。

题目描述

给定一个 $n×n$ 的网格，表示森林的地图。每个格子要么为空，要么有一棵树。你的任务是处理 $q$ 个查询，查询有以下两种类型：

1. 修改一个格子的状态（从空格变为树，或者从树变为空格）。
2. 查询一个矩形区域内有多少棵树。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示森林的大小和查询的数量。

接下来有 $n$ 行，每行包含 $n$ 个字符：. 代表空格， * 代表树。

然后有 $q$ 行，每行描述一个查询。查询的格式有两种：

• 1 y x：表示将位置 $(y,x)$ 的状态改变，若原本是树则变为空格，若原本是空格则变为树。
• 2 y1 x1 y2 x2：表示查询矩形区域 $(y_1,x_1)$ 到 $(y_2,x_2)$ 内有多少棵树。

输出格式

对于每个类型为 2 的查询，输出该矩形区域内的树的数量。

样例

4 3
.*..
*.**
**..
****
2 2 2 3 4
1 3 3
2 2 2 3 4

3
4

说明/提示

$1 \leq n \leq 1000$；

$1 \leq q \leq 2 \cdot 10^5$；

$1 \leq y,x \leq n$；

$1 \leq y_1 \leq y_2 \leq n$；

$1 \leq x_1 \leq x_2 \leq n$。