← 返回题目列表

AtCoder · soundhound2018_summer_final_e

E. 哈希交换

中文机器翻译题面 查看原题

配点 : 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