Số lần lặp xâu

Với một xâu $x$ và một số nguyên dương $n$, ký hiệu $[x,n]$ là xâu thu được khi nối $n$ bản sao của $x$ liên tiếp. Ví dụ $[\text{abc},2]=\text{abcabc}$.

Ta nói xâu $s$ có thể thu được từ xâu $t$ nếu có thể xóa bớt một số ký tự của $t$ (giữ nguyên thứ tự các ký tự còn lại) để được đúng $s$. Nói cách khác, $s$ là một xâu con (subsequence) của $t$. Ví dụ, từ xâu $\text{xacbac}$ có thể thu được $\text{ab}$ và $\text{acba}$, nhưng không thu được $\text{bx}$ hay $\text{aaa}$.

Cho hai xâu $w=[a,b]$ và $q=[c,d]$. Hãy tìm số nguyên $p$ lớn nhất ($p>0$) sao cho $[q,p]$ có thể thu được từ $w$. Nếu không tồn tại giá trị $p$ nào thỏa mãn, in ra $0$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $b$, $d$.
• Dòng thứ hai chứa xâu $a$.
• Dòng thứ ba chứa xâu $c$.

Các xâu đều khác rỗng và chỉ gồm các chữ cái Latin thường.

Dữ liệu ra

In ra một số nguyên duy nhất là giá trị $p$ lớn nhất. Nếu không tồn tại, in ra $0$.

Ràng buộc

• $1\le b,d\le {10}^7$
• $1\le |a|,|c|\le 100$

Ví dụ