I. Prefixes on segments Upsolve

You are given n strings, the length of each of them is m. You are given q queries, for each query

• You are given l,r,k numbers. For strings in the interval [l,r], how many unique strings are there if for each string we take the prefix of length k?

The first line contains two natural numbers n,m(1≤n∗m≤106).

The following lines contain strings of length m. The lines consist of lowercase Latin letters.

The number of queries is given in the next line, q(1≤q≤2∗105).

The following q lines give the query parameters, x,y,k(1≤x,y≤106,1≤k≤m).

Please note that you are provided with the values ​​of the x and y, for the query l and r is calculated as follows:

 l=(x+prev_ans−1)modn+1

 r=(y+prev_ans−1)modn+1

Here prev_ans means the answer to the previous query. For the first query prev_ans=0.

If the query resulted in l>r, their values ​​should be swapped.                                            

Print the answer for each query.