You are given two strings $S$ and $T$, where some positions are marked with *, which can represent any character.
Find all $1 \leq i \leq |T| - |S|+1$ such that $T[i:i+|S|-1]=S$ could possibly hold.
Input
The input consists of two lines, representing the strings $S$ and $T$ respectively.
Output
Output a single line containing several integers, representing all matching positions in increasing order.
Subtasks
For all data, $1 \leq |S|, |T| \leq 3 \times 10^5$. It is guaranteed that only lowercase English letters and * will appear.
- Subtask 1 (20 pts): $|S|, |T| \leq 1000$.
- Subtask 2 (40 pts): $|S|, |T| \leq 4 \times 10^4$.
- Subtask 3 (40 pts): No additional constraints.
Examples
Input 1
a*b acbc*cb
Output 1
1 5
Input 2
*** *****
Output 2
1 2 3
Input 3
e*e the*results*of*the*siberian*grand*prix*will*be*added*to*the*rating*after*******gmt*nov****after*the*widesiberian*olympiad*closing*ceremony**where*the*last*hour*for*the*base*contest*teams*will*be*opened*
Output 3
4 44 51 71 73 74 75 76 77 87 88 94 130 132 143 181 192 198 200