Se dau două şiruri de caractere $A$ şi $B$ şi un număr natural $K$. Se cere să se spună pe câte poziţii şirul $A$ se "aproape-potriveşte" peste şirul $B$.

Un şir $A$ se "aproape-potriveşte" peste un alt şir $B$ pe o poziţie $i (0 &le; i < |B|)$, dacă $i + |A| &le; |B|$ şi există cel mult $K$ poziţii $j (0 &le; j < |A|)$, pentru care $A[j] != B[i + j]$.

Un şir $A$ se "aproape-potriveşte" peste un alt şir $B$ pe o poziţie $i (0 &le; i < |B|), dacă $i + |A| - 1 <= |B|$ şi există cel mult $K$ poziţii $j (0 &le; j < |A|)$, pentru care $A[j] != B[i + j]$.

h2. Date de intrare

* $1 ≤ |A|, |B| ≤ 100.000$
* $0 ≤ K ≤ 10$

* $Cele două şiruri conţin doar caractere din alfabetul latin.$
* $Numerotarea caracterelor începe cu poziţia 0.$

h2. Exemplu

| 2
0
3

|
| baa
ccba
1
| 0
|

|

h3. Explicaţie

10110