E - Hash Swapping Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点 : 800

問題文

英小文字からなる長さNの文字列が M 個与えられ、 S_1, S_2, ..., S_M とします。以下のクエリを Q 個処理して下さい。

  • swapクエリ(type = 1, x, y, l, r): S_x[l..r]S_y[l..r] をswapする。
  • hashクエリ(type = 2, x, y = 0, l, r): h(S_x[l..r]) を求め,出力する。

なお、

  • 文字列 S に対し、S[l..r] を、Sl文字目からr文字目まで(両端含む)の部分文字列を表すこととします。
  • 英小文字 a に対し、ord(a) = 1, ord(b) = 2, ..., ord(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
  • swapクエリのとき, x_i < y_i \leq M
  • hashクエリのとき、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

出力

各hashクエリに対し、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