Substring Search

Given a long text t and a string s, you are asked to find all the occurrences of s in the text t. You are asked to find the starting positions in t that match s.

Input

The first line of the input contains the text t (1 ≤ |t| ≤ ).
The second line of the input contains the string s (1 ≤ |s| ≤ |t|).

Output

For each occurrence of s in t, output the starting position in t where it occurs. The positions should be in ascending order (from the beginning of the text to the end) separated by a space. The indexing starts from 0.

Examples

Input
Output
habababohabo ba
2 4
barfoobarfoobarfoobarfoobarfoo foobarfoo
3 9 15 21

Explanation

  1. habababohabo → habababohabo, habababohabo
  1. barfoobarfoobarfoobarfoobarfoo → barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo, barfoobarfoobarfoobarfoobarfoo
 

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue