Find places where a string P is found within a text T. Print all indices of T where P found. The indices of T start with 0.

Constraints

* 1 ≤ length of T ≤ 1000000
* 1 ≤ length of P ≤ 10000
* The input consists of alphabetical characters and digits

Input

In the first line, a text T is given. In the second line, a string P is given.

Output

Print an index of T where P found in a line. Print the indices in ascending order.

Examples

Input

aabaaa
aa


Output

0
3
4


Input

xyzz
yz


Output

1


Input

abc
xyz


Output
import sys
input = sys.stdin.readline

def make_table(s):
    n = len(s)
    res = [-1]*(n+1)
    j = -1
    
    for i in range(n):
        while j>=0 and s[i]!=s[j]:
            j = res[j]
        
        j += 1
        res[i+1] = j
    
    return res

def kmp(s, w): #s中のwと一致する箇所の先頭インデックスのリストを作成
    table = make_table(w)
    res = []
    m, i, n = 0, 0, len(s)
    
    while m+i<n:
        if w[i]==s[m+i]:
            i += 1
            
            if i==len(w):
                res.append(m)
                m = m+i-table[i]
                i = table[i]
        else:
            m = m+i-table[i]
            
            if i>0:
                i = table[i]
    
    return res

T = input()[:-1]
P = input()[:-1]
res = kmp(T, P)

for res_i in res:
    print(res_i)
