Educational Codeforces Round 21 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

strings

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Anthem of Berland

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBerland 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".

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2024 07:34:36 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|