AT_soundhound2018_summer_final_e Hash Swapping

给定 $M$ 个仅由小写英文字母组成、长度为 $N$ 的字符串，记为 $S_1, S_2, \ldots, S_M$。请处理 $Q$ 个如下类型的查询： - swap 查询（$type = 1, x, y, l, r$）：将 $S_x[l..r]$ 与 $S_y[l..r]$ 进行交换。 - hash 查询（$type = 2, x, y = 0, l, r$）：计算 $h(S_x[l..r])$ 并输出。 其中： - 对于字符串 $S$，$S[l..r]$ 表示 $S$ 的第 $l$ 个字符到第 $r$ 个字符（包含两端）的子串。 - 对于小写字母 $a$，定义 $\mathrm{ord}(a) = 1, \mathrm{ord}(b) = 2, \ldots, \mathrm{ord}(z) = 26$。 - 对于字符串 $S = c_1c_2\ldots c_k$，定义 $h(S) = \left(\sum_{i=1}^k \mathrm{ord}(c_i) \cdot (1,000,000)^{i-1}\right) \bmod (10^9 + 7)$。

输入按以下格式从标准输入给出。 > $N$ $M$ > $S_1$ > $S_2$ > $\vdots$ > $S_M$ > $Q$ > $type_1$ $x_1$ $y_1$ $l_1$ $r_1$ > $type_2$ $x_2$ $y_2$ $l_2$ $r_2$ > $\vdots$ > $type_Q$ $x_Q$ $y_Q$ $l_Q$ $r_Q$

对于每个 hash 查询，输出 $h(S_x[l..r])$。

### 数据范围 - $1 \leq N \leq 200,\!000$ - $1 \leq M \leq 20$ - $S_i$ 仅包含小写英文字母 - $1 \leq Q \leq 200,\!000$ - $type_i = 1$ 或 $2$ - $1 \leq x_i \leq M$ - 对于 swap 查询，$x_i < y_i \leq M$ - 对于 hash 查询，$y_i = 0$ - $1 \leq l_i \leq r_i \leq N$ ### 样例解释 1 分别输出： - $h(\text{"bc"}) = 3000002$ - $h(\text{"fghij"}) = 496944447$ - $h(\text{"gc"}) = 3000007$ - $h(\text{"fbhij"}) = 491944447$ - $h(\text{"bh"}) = 8000002$ - $h(\text{"agcij"}) = 496979442$ 由 ChatGPT 4.1 翻译