Dreamoon và những xâu ký tự

Cho một xâu $s$ và một xâu mẫu $p$. Với một số nguyên $x$, ta xoá đúng $x$ ký tự khỏi $s$ (các ký tự còn lại giữ nguyên thứ tự) để thu được xâu $s^{\prime }$. Sau đó ta tính số lượng lớn nhất các xâu con liên tiếp, không giao nhau của $s^{\prime }$ mà bằng đúng $p$.

Gọi giá trị đó là $f(x)$: số bản sao $p$ nhiều nhất có thể ghép được, lấy tối đa trên tất cả các cách xoá đúng $x$ ký tự khỏi $s$.

Hãy tính $f(x)$ cho mọi $x$ từ $0$ đến $|s|$.

Dữ liệu vào

• Dòng thứ nhất chứa xâu $s$.
• Dòng thứ hai chứa xâu mẫu $p$.

Cả hai xâu chỉ gồm các chữ cái Latinh thường.

Dữ liệu ra

In ra $|s|+1$ số nguyên cách nhau bởi dấu cách trên một dòng: lần lượt là $f(0),f(1),\dots ,f(|s|)$.

Ràng buộc

• $1\le |s|\le 2000$
• $1\le |p|\le 500$

Ví dụ