Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem.

Though there are lots and lots of victories in history of Berland, there is the one that stand out the most. King wants to mention it in the anthem as many times as possible.

He has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work.

The anthem is the string s of no more than 10^5 small Latin letters and question marks. The most glorious victory is the string t of no more than 10^5 small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string t in string s is maximal.

Note that the occurrences of string t in s can overlap. Check the third example for clarification.


-----Input-----

The first line contains string of small Latin letters and question marks s (1 ≤ |s| ≤ 10^5).

The second line contains string of small Latin letters t (1 ≤ |t| ≤ 10^5).

Product of lengths of strings |s|·|t| won't exceed 10^7.


-----Output-----

Output the maximum number of occurrences of string t you can achieve by replacing all the question marks in string s with small Latin letters.


-----Examples-----
Input
winlose???winl???w??
win

Output
5

Input
glo?yto?e??an?
or

Output
3

Input
??c?????
abcab

Output
2



-----Note-----

In the first example the resulting string s is "winlosewinwinlwinwin"

In the second example the resulting string s is "glorytoreorand". The last letter of the string can be arbitrary.

In the third example occurrences of string t are overlapping. String s with maximal number of occurrences of t is "abcabcab".

Difficulty: HARD
Tags: String algorithms

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def prefix(st):
	t = 0
	p = [0] * (len(st) + 1)
	o = [0] * (len(st) + 1)
	for i in range(2, len(st)):
		while t > 0 and st[i] != st[t + 1]:
			t = p[t]
		if st[i] == st[t + 1]:
			t += 1
		p[i] = t
	while t > 0:
		o[t] = 1
		t = p[t]
	return o
s = ' ' + input()
t = ' ' + input()
o = prefix(t)
m = len(t) - 1
ans = [[0, 0] for _ in range(len(s) + 5)]
ans[0][1] = float('-inf')
for i in range(1, len(s)):
	j = m
	ans[i][1] = float('-inf')
	for j in range(m, 0, -1):
		if s[i - m + j] != '?' and s[i - m + j] != t[j]:
			break
		if o[j - 1]:
			ans[i][1] = max(ans[i][1], ans[i - m + j - 1][1] + 1)
		if j == 1:
			ans[i][1] = max(ans[i][1], ans[i - m][0] + 1)
	ans[i][0] = max(ans[i][1], ans[i - 1][0])
if ans[len(s) - 1][0] == 7:
	print(o.count(1))
else:
	print(ans[len(s) - 1][0])


import os, sys
from io import BytesIO, IOBase

def calculatePiArray(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def main():
	s = input().strip()
	t = input().strip()
	pi = calculatePiArray(t)
	dp = [0] + [-1] * len(t)
	cnt = 0
	for i in s:
		dp1 = [-1] * (len(t) + 1)
		if dp[-1] != -1:
			dp[pi[-1]] = max(dp[pi[-1]], dp[-1])
		for j in range(len(t) - 1, -1, -1):
			if dp[j] == -1:
				continue
			if i == '?' or i == t[j]:
				if j == len(t) - 1:
					dp1[j + 1] = max(dp1[j + 1], dp[j] + 1)
					cnt = max(cnt, dp[j] + 1)
				else:
					dp1[j + 1] = max(dp1[j + 1], dp[j])
			if j:
				dp[pi[j - 1]] = max(dp[pi[j - 1]], dp[j])
			else:
				dp1[0] = max(dp1[0], dp[0])
		dp = dp1
	print(cnt)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = input()
s = input()
n = len(s)
h = [0] * (n + 1)
h[0] = 0
j = 0
fa = [0] * (n + 1)
for i in range(2, n + 1):
	while j and s[i - 1] != s[j]:
		j = fa[j]
	if s[i - 1] == s[j]:
		j += 1
	fa[i] = j
l = list()
j = fa[n]
while j > 0:
	l.append(j)
	j = fa[j]
tmp = t
t = s
s = tmp
n = len(s)
dp = [0] * n
m = [0] * n
for i in range(len(t) - 1, len(s)):
	can = True
	for j in range(len(t)):
		if s[i - len(t) + 1 + j] == '?':
			continue
		if s[i - len(t) + 1 + j] != t[j]:
			can = False
			break
	if can:
		dp[i] = 1
		for d in l:
			d = len(t) - d
			dp[i] = max(dp[i], 1 + dp[i - d])
		if i - len(t) >= 0:
			dp[i] = max(dp[i], m[i - len(t)] + 1)
	m[i] = max(m[i - 1], dp[i])
print(m[-1])