描述
小B正在使用一款文字校对软件，检查两行文字是否一致。两行文字都由 $n$ 个小写英文字母组成，分别记为 $s$ 和 $t$。每一行中的字符位置从左到右编号为 $1,2,\ldots,n$。
每个位置 $i$ 都有一个给定的差异分值 $w_i$。检查一段文字时，对于其中每个未被遮挡且两行文字对应字符不同的位置，都将 $w_i$ 计入这次检查的总分。
软件可以暂时遮挡一段位置。一次遮挡会同时作用于两行文字，不会删除字符，也不会改变位置编号。多个遮挡可以重叠；只要一个位置被至少一个当前有效的遮挡覆盖，检查时就不计入这个位置的分值。一次遮挡失效，只会取消这一次遮挡，不会取消其他仍然有效的遮挡。
开始时没有任何遮挡。接下来共有 $q$ 次操作，第 $j$ 次操作发生在时刻 $j$。操作有以下三种：
1. **添加遮挡。** 给出 $l,r,e$，遮挡第 $l$ 个位置到第 $r$ 个位置，包括两个端点。这次遮挡从当前时刻开始生效，并在时刻 $e$ 开始时失效，因此不覆盖第 $e$ 次及之后的操作。保证 $j<e\le q+1$。当 $e=q+1$ 时，这次遮挡在剩余的所有操作期间都有效。
2. **修改字符。** 给出 $a,p,c$，把第 $a$ 行文字的第 $p$ 个字符改成 $c$。其中 $a=1$ 表示第一行，$a=2$ 表示第二行。即使这个位置正在被遮挡，也可以修改，修改立即生效。遮挡只影响是否计入分值，不会阻止字符的修改。
3. **检查文字。** 给出 $l,r$，计算第 $l$ 个位置到第 $r$ 个位置中，没有被遮挡且两行对应字符不同的位置的分值总和，包括两个端点。
每个时刻先取消在这一时刻失效的全部遮挡，再执行这一时刻的操作。每个位置的分值 $w_i$ 始终不变。
请依次回答每次检查文字的结果。
输入
第一行包含一个整数 $T$，表示数据组数。对于每组数据：
第一行包含两个整数 $n,q$，分别表示每行文字的长度和操作次数。
第二行包含字符串 $s$，第三行包含字符串 $t$。
第四行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$，表示各个位置的差异分值。
接下来有 $q$ 行，第 $j$ 行描述第 $j$ 次操作。每行第一个整数表示操作类型，格式如下：
- `1 l r e`：添加一次遮挡，含义见题目描述；
- `2 a p c`：把第 $a$ 行文字的第 $p$ 个字符修改为小写英文字母 $c$；
- `3 l r`：检查第 $l$ 个位置到第 $r$ 个位置，求对应的分值总和。
输出
对于每次类型为 $3$ 的操作，输出一行，包含一个整数，表示这次检查得到的总分。不同数据组的结果之间不需要输出额外的空行。
样例
- 复制
- 复制
提示
## 样例解释
第 $1$ 组数据中，开始时只有第 $2$ 个位置和第 $4$ 个位置的字符不同，所以第 $1$ 次操作得到 $3+7=10$ 分。
第 $2$ 次操作遮挡位置 $2$ 至 $4$，在第 $7$ 次操作开始前失效；第 $3$ 次操作遮挡位置 $3$ 至 $5$，在第 $9$ 次操作开始前失效。
第 $4$ 次操作把第一行的第 $3$ 个字符改为 `z`。这个位置虽然正在被遮挡，字符仍然会改变。第 $5$ 次操作检查时，位置 $2$ 至 $5$ 都被遮挡，位置 $1$ 的两个字符相同，所以结果为 $0$。
第 $6$ 次操作把第二行的第 $2$ 个字符改为 `z`。第 $7$ 次操作开始前，第一次遮挡失效，但第二次遮挡仍然有效，因此位置 $3$ 至 $5$ 仍被遮挡。只有位置 $2$ 产生分值，结果为 $3$。
第 $8$ 次操作把第二行的第 $4$ 个字符改为 `d`。第 $9$ 次操作开始前，第二次遮挡也失效，此时两行文字分别为 `abzde` 和 `azcde`。位置 $2$ 和位置 $3$ 的字符不同，第 $9$ 次操作得到 $3+5=8$ 分。第 $10$ 次操作只检查位置 $3$ 至 $5$，结果为 $5$。
第 $2$ 组数据中，唯一的位置被先后添加的两次遮挡覆盖。第 $3$ 次操作开始前，只有第一次遮挡失效，第二次遮挡仍然有效，所以结果为 $0$。第 $4$ 次操作开始前，第二次遮挡也失效，两行字符不同，结果为 $10^9$。第 $5$ 次操作将第二行字符修改为 `a` 后，两行字符相同，第 $6$ 次操作得到 $0$ 分。
## 数据范围与测试点
对于所有数据，保证：
- $1\le T\le20$；
- $1\le n,q\le2\times10^5$；
- 同一输入文件中，所有数据组的 $n$ 之和不超过 $2\times10^5$，$q$ 之和也不超过 $2\times10^5$；
- 字符串 $s,t$ 的长度都为 $n$，只包含小写英文字母；
- $0\le w_i\le10^9$；
- 对于类型为 $1$、$3$ 的操作，$1\le l\le r\le n$；
- 第 $j$ 次操作若属于类型 $1$，则 $j<e\le q+1$；
- 对于类型为 $2$ 的操作，$a\in\{1,2\}$，$1\le p\le n$，$c$ 为小写英文字母。
下表中的限制对对应测试点中的每组数据均成立。“—”表示除上述通用数据范围外，没有额外限制。
| 测试点编号 | 数据规模 | 特殊性质 | 分值 |
|:---:|:---:|:---:|:---:|
| 1 | $n,q\le2000$ | — | 5 |
| 2 | $n,q\le2000$ | — | 5 |
| 3 | $n,q\le2000$ | — | 5 |
| 4 | $n,q\le2000$ | — | 5 |
| 5 | — | A | 5 |
| 6 | — | A | 5 |
| 7 | — | B | 5 |
| 8 | — | B | 5 |
| 9 | — | B | 5 |
| 10 | — | C | 5 |
| 11 | — | C | 5 |
| 12 | — | D | 5 |
| 13 | — | D | 5 |
| 14 | — | — | 5 |
| 15 | — | — | 5 |
| 16 | — | — | 5 |
| 17 | — | — | 5 |
| 18 | — | — | 5 |
| 19 | — | — | 5 |
| 20 | — | — | 5 |
**特殊性质 A：**没有类型为 $1$ 的操作。
**特殊性质 B：**所有类型为 $1$ 的操作均满足 $l=r$。
**特殊性质 C：**类型为 $3$ 的操作至多出现一次。
**特殊性质 D：**所有类型为 $1$ 的操作均满足 $e=q+1$。
每个测试点单独计分，每个测试点为 $5$ 分，总分为 $100$ 分。同一测试点输入文件中的所有查询都回答正确时，获得该测试点的分值。
关注我们
