Problem Description

Given \( M \) strings of length \( N \) consisting of lowercase English letters, denoted as \( S_1, S_2, \ldots, S_M \). Process \( Q \) queries of the following types:

• swap query (\( type = 1, x, y, l, r \)): Swap \( S_x[l..r] \) and \( S_y[l..r] \).
• hash query (\( type = 2, x, y = 0, l, r \)): Compute and output \( h(S_x[l..r]) \).

Additionally,

• For a string \( S \), \( S[l..r] \) represents the substring from the \( l \)-th to the \( r \)-th character (inclusive).
• For a lowercase English letter \( a \), ord(\( a \)) = 1, ord(\( b \)) = 2, ..., ord(\( z \)) = 26.
• For a string \( S = c_1c_2...c_k \), \( h(S) \) is defined as \( \sum_{i=1..k} {\rm ord}(c_i)(1,000,000)^{i-1} \) modulo \( 10^9 + 7 \).

Input Format

The input is given from the standard input in the following format:

\( 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 \)

Output Format

For each hash query, output \( h(S_x[l..r]) \).

Sample Input and Output

Sample Input #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

Sample Output #1

3000002
496944447
3000007
491944447
8000002
496979442

Sample Input #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

Sample Output #2

26000016
21
17000008
556958241
25847241

Notes/Hints

Constraints

• \( 1 \leq N \leq 200,000 \)
• \( 1 \leq M \leq 20 \)
• \( S_i \) consists only of lowercase English letters.
• \( 1 \leq Q \leq 200,000 \)
• \( type_i = 1, 2 \)
• \( 1 \leq x_i \leq M \)
• For swap queries, \( x_i < y_i \leq M \)
• For hash queries, \( y_i = 0 \)
• \( 1 \leq l_i \leq r_i \leq N \)

Sample Explanation 1

Each output corresponds to:
- \( h("bc") = 3000002 \)
- \( h("fghij") = 496944447 \)
- \( h("gc") = 3000007 \)
- \( h("fbhij") = 491944447 \)
- \( h("bh") = 8000002 \)
- \( h("agcij") = 496979442 \)

见题面 Input 部分

见题面 Output 部分