AT_soundhound2018_summer_final_e Hash Swapping

[problemUrl]: https://atcoder.jp/contests/soundhound2018-summer-final/tasks/soundhound2018_summer_final_e 英小文字からなる長さ$ 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] $ を、$ S $の$ l $文字目から$ 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) $ とします。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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\