B. Segment Occurrences

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two strings s and t , both consisting only of lowercase Latin letters.

The substring s[l..r] is the string which is obtained by taking characters sl,sl+1,…,sr without changing the order.

Each of the occurrences of string a in a string b is a position i (1≤i≤|b|−|a|+1 ) such that b[i..i+|a|−1]=a (|a| is the length of string a ).

You are asked q queries: for the i -th query you are required to calculate the number of occurrences of string t in a substring s[li..ri] .

Input

The first line contains three integer numbers n , m and q (1≤n,m≤103 , 1≤q≤105 ) — the length of string s , the length of string t and the number of queries, respectively.

The second line is a string s (|s|=n ), consisting only of lowercase Latin letters.

The third line is a string t (|t|=m ), consisting only of lowercase Latin letters.

Each of the next q lines contains two integer numbers li and ri (1≤li≤ri≤n ) — the arguments for the i -th query.

Output

Print q lines — the i -th line should contain the answer to the i -th query, that is the number of occurrences of string t in a substring s[li..ri] .

Examples

Input

Copy

10 3 4 codeforces for 1 3 3 10 5 6 5 7

Output

Copy

0 1 0 1

Input

Copy

15 2 3 abacabadabacaba ba 1 15 3 4 2 14

Output

Copy

4 0 3

Input

Copy

3 5 2 aaa baaab 1 3 1 1

Output

Copy

0 0

Note

In the first example the queries are substrings: "cod", "deforces", "fo" and "for", respectively.

 

 

题目大意：就是给两个字符串s t，然后q次查询，给出 [l, r], 问t出现的次数。

刚开始做这道题感觉就是瞎写，没有好好思考，下面给出官方的思路：首先看一下单纯的做法。q次查询，每次从 i 属于 [l, r-m+1] 然后遍历，看是否和t一样。时间复杂度(q*m*n).

注意到t只能从s的n个位置开始，我们可以预处理t出现的位置，然后前缀和维护出现次数，这样的话，每次查询都是O(1).

 

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 #include