配点 : 800 点
問題文
的字符串为N的字符串 M 个,第 S_1, S_2, ..., S_M 。请处理以下查询 Q 。 交换
- swapkueri(type = 1, x, y, l, r): S_x[l..r] 和 在S_y[l..r] 。 求出
- hashkueri(type = 2, x, y = 0, l, r): h(S_x[l..r]) 并输出。 针对
此外,
- 文字列 S ,S[l..r] 的,S的l表示从第几个字符开始r到第几个字符结束(包括两端)的子字符串。
- 英小文字 a 对应,取ord(a) = 1, 订单(b) = 2, ..., 订单(z) = 26 被记作。
- 文字列 S = c_1c_2...c_k ,\sum_{i=1..k} {\rm ord}(c_i)(1,000,000)^{i-1} 在 10^9 + 7 的余数 h(S) 被记作。
制約
- 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
- 交换kueri时, x_i < y_i \leq M
- hashkueri时,y_i = 0
- 1 \leq l_i \leq r_i \leq N
入力
输入是按以下格式从标准输入给出的。
N M S_1 S_2 : S_M Q type_1 x_1 y_1 l_1 r_1 type_2 x_2 y_2 l_2 r_2 : type_Q x_Q y_Q l_Q r_Q
出力
对每个hashkueri,h(S_x[l..r]) 请输出。
入力例 1
5 2 abcde fghij 8 2 1 0 2 3 2 2 0 1 5 1 1 2 2 2 2 1 0 2 3 2 2 0 1 5 1 1 2 1 3 2 1 0 2 3 2 2 0 1 5
出力例 1
3000002 496944447 3000007 491944447 8000002 496979442
各自,
- h("bc") = 3000002
- h("fghij") = 496944447
- h("gc") = 3000007
- h("fbhij") = 491944447
- h("bh") = 8000002
- h("agcij") = 496979442
。 与
入力例 2
7 3 pzocuwt ghqsktw ogvyhak 13 2 1 0 1 2 1 1 2 5 6 1 1 3 3 6 1 2 3 4 5 1 2 3 5 6 1 1 2 1 6 1 1 2 5 6 2 2 0 5 5 2 1 0 2 3 1 2 3 1 4 1 1 2 2 7 2 3 0 1 6 2 3 0 1 4
出力例 2
26000016 21 17000008 556958241 25847241