Quang có một xâu ~s~ và xâu ~p~. Đầu tiên Quang xóa ~x~ kí tự bất kì của ~s~ để nhận được xâu ~s'~. Sau đó Quang tính số lần lặp lại (không chồng nhau) của ~p~ trong xâu ~s'~. Quang muốn con số này lớn nhất có thể.

Nói cách khác, Quang tính giá trị lớn nhất của số lần lặp lại (không chồng nhau) của ~p~ trong mọi ~s'~ có thể được tạo bởi khi xóa ~x~ kí tự từ ~s~. Quang muốn biết với mọi ~x~ từ ~0~ tới ~|s|~ với ~|s|~ là độ dài xâu ~s~.

Input

• Dòng đầu chứa xâu ~s~ ~(1 \le |s| \le 2000)~.

• Dòng thứ hai chứa xâu ~p~ ~(1 \le |p| \le 500)~.

Cả hai xâu đảm bảo chỉ chứa các kí tự tiếng Anh in thường.

Output

• In ra ~|s|+1~ số nguyên riêng biệt cho mọi ~x~ từ ~0~ tới ~|s|~.

Scoring

Sample Input 1

aaaaa
aa

Sample Output 1

2 2 1 1 0 0

Sample Input 2

axbaxxb
ab

Sample Output 2

0 1 1 2 1 1 0 0

Notes

• Trong ví dụ thứ nhất, giá trị ~s'~ sau khi xóa từ ~0~ tới ~|s|=5~ kí tự từ ~s~ là ~\{~"aaaaa", "aaaa", "aaa", "aa", "a", ""~\}~.

• Trong ví dụ thứ hai, giá trị ~s'~ là ~\{~"axbaxxb", "abaxxb", "axbab", "abab", "aba", "ab", "a", ""~\}~.