Description

Long ago, when you had just learned string matching, there were two strings $A$ and $B$ containing only lowercase letters, with lengths $m$ and $n$ respectively. Now, when you encounter these two strings again, they have aged; each string has become partially damaged.

You want to match the two strings again, taking $A$ as the pattern. For every position $i$ in $B$, determine whether the length-$m$ substring starting at this position could exactly match string $A$.

Input Format

The first line contains two positive integers $m, n$, representing the lengths of strings $A$ and $B$ respectively.

The second line contains a string $A$ of length $m$.

The third line contains a string $B$ of length $n$.

Both strings consist only of lowercase letters and $\texttt *$, where $\texttt *$ indicates that the corresponding position is damaged and each $\texttt *$ can match any single lowercase letter.

Output Format

The first line contains an integer $k$, the number of starting positions in $B$ where $A$ can exactly match.

If $k > 0$, then on the second line output $k$ positive integers in increasing order, each being a valid starting position (indices start from $1$).

3 7
a*b
aebr*ob

2
1 5

Hint

For $100\%$ of the testdata, $1 \le m \le n \le 3 \times 10^5$.

Translated by ChatGPT 5