题干：

A string t is called an anagram of the string s, if it is possible to rearrange letters in t so that it is identical to the string s. For example, the string "aab" is an anagram of the string "aba" and the string "aaa" is not.

The string t is called a substring of the string s if it can be read starting from some position in the string s. For example, the string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba".

You are given a string s, consisting of lowercase Latin letters and characters "?". You are also given a string p, consisting of lowercase Latin letters only. Let's assume that a string is good if you can obtain an anagram of the string p from it, replacing the "?" characters by Latin letters. Each "?" can be replaced by exactly one character of the Latin alphabet. For example, if the string p = «aba», then the string "a??" is good, and the string «?bc» is not.

Your task is to find the number of good substrings of the string s (identical substrings must be counted in the answer several times).

Input

The first line is non-empty string s, consisting of no more than 105 lowercase Latin letters and characters "?". The second line is non-empty string p, consisting of no more than 105 lowercase Latin letters. Please note that the length of the string pcan exceed the length of the string s.

Output

Print the single number representing the number of good substrings of string s.

Two substrings are considered different in their positions of occurrence are different. Thus, if some string occurs several times, then it should be counted the same number of times.

Examples

Input

bb??x???
aab

Output

2

Input

ab?c
acb

Output

2

Note

Consider the first sample test. Here the string s has two good substrings: "b??" (after we replace the question marks we get "baa"), "???" (after we replace the question marks we get "baa").

Let's consider the second sample test. Here the string s has two good substrings: "ab?" ("?" can be replaced by "c"), "b?c" ("?" can be replaced by "a").

题目大意：

首先告诉你了两个定义：1.字符串的异构（其实就是当前串的某个排列），2.子字符串，3.good string。

给你两个字符串，如果s的子字符串中有和p的某个排列完全相同的，就可以说这个子字符串是符合条件的。S字符串有小写字母和 ' ? ' 组成，而 ' ? ' 可以替换为任意的字母。最后问你，有多少个符合条件的子字符串。（子字符串是连续的若干个字符）

解题报告：

这种字符串涉及排列的，，显然要计数一下的。因为包含p字符串中的所有字母及对应个数相同的话，那么就可以满足。类似这道题【CodeForces - 1038A 】Equality （思维水题，预处理字符串）。

实现的话滑窗法就好了呀，用一个长度为len2的窗口，从头滑到尾，顺便维护字符出现的个数和ans就好。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAX = 1e5 +5;
int bk[555],cnt[555],ans;
char s[MAX],p[MAX];
int main()
{
	cin>>(s+1);
	cin>>(p+1);
//	printf("%d",'?');
	int len1 = strlen(s+1);
	int len2 = strlen(p+1);
	if(len2 > len1) {
		puts("0");return 0;
	}
	for(int i = 1; i<=len2; i++) bk[p[i]]++;
	int l = 1,r = len2;
	for(int i = l; i<=r-1; i++) cnt[s[i]]++;
	while(r <= len1) {
		cnt[s[l-1]]--;
		cnt[s[r]]++;
		int rest = 0,flag = 1;
		for(int i = 'a'; i<='z'; i++) {
			if(cnt[i] > bk[i] ) {
				flag = 0;break;
			}
			if(cnt[i] < bk[i] ) rest +=  bk[i] - cnt[i];
		}
		if(flag && rest == cnt['?']) ans++;
		
		l++,r++;
	}
	printf("%d\n",ans);
	return 0 ;
}

总结：注意为了统一形式，while上面那个for只能处理到r-1，然后相当于l=1，r=len2再开始处理，不然就得特判一下。。