Segment Occurrences

http://codeforces.com/problemset/problem/1016/B

在网上找了一个题解，感觉有点东西，用substr不断取出长度为m的子串，并记录下来，查询的时候直接枚举查询的区间。

用substr的时候定义字符串要用string,输入字符串的时候要用cin，否则会出现错误，不知道为啥，还是记下吧

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.

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include<stdlib.h>
#include<cmath>
#include<map>
using namespace std;
typedef long long int LL;
const LL MAXL(1e5);

int main()
{
	int n,m,t,s[10000],k,l,r,i,ans;
	string a,b;
	while(~scanf("%d%d%d",&n,&m,&t))
    {
		memset(s,0,sizeof(s));
		cin>>a>>b;
		for(i=0;i<=n-m;i++)
            if(a.substr(i,m)==b)
               s[i]=1;
        while(t--)
        {
            ans=0;
            scanf("%d%d",&l,&r);
            for(i=l-1;i<=r-m;i++)
                if(s[i])
                    ans++;
            printf("%d\n",ans);
        }
	}
	return 0;
}