Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

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.

No tag edit access

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

×
E. Dreamoon and Strings

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDreamoon has a string *s* and a pattern string *p*. He first removes exactly *x* characters from *s* obtaining string *s*' as a result. Then he calculates that is defined as the maximal number of non-overlapping substrings equal to *p* that can be found in *s*'. He wants to make this number as big as possible.

More formally, let's define as maximum value of over all *s*' that can be obtained by removing exactly *x* characters from *s*. Dreamoon wants to know for all *x* from 0 to |*s*| where |*s*| denotes the length of string *s*.

Input

The first line of the input contains the string *s* (1 ≤ |*s*| ≤ 2 000).

The second line of the input contains the string *p* (1 ≤ |*p*| ≤ 500).

Both strings will only consist of lower case English letters.

Output

Print |*s*| + 1 space-separated integers in a single line representing the for all *x* from 0 to |*s*|.

Examples

Input

aaaaa

aa

Output

2 2 1 1 0 0

Input

axbaxxb

ab

Output

0 1 1 2 1 1 0 0

Note

For the first sample, the corresponding optimal values of *s*' after removal 0 through |*s*| = 5 characters from *s* are {"aaaaa", "aaaa", "aaa", "aa", "a", ""}.

For the second sample, possible corresponding optimal values of *s*' are {"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""}.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/22/2021 06:25:11 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|