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
def rolliha(t, p):
    b = 1007
    h = 1000000007
    n = len(t)
    m = len(p)
    if n < m:
        return
    thsh = 0
    phsh = 0
    bpow = [1 for i in range(m+1)]
    for i in range(m):
        bpow[i+1] = bpow[i]*b % h
    for i in range(m):
        thsh = (thsh+bpow[m-1-i]*ord(t[i])) % h
        phsh = (phsh+bpow[m-1-i]*ord(p[i])) % h
    if thsh == phsh:
        print(0)
    ind = 0
    while ind+m < n:
        thsh = ((thsh*b % h) - bpow[m]*ord(t[ind]) + ord(t[ind+m])) % h
        if thsh == phsh:
            print(ind+1)
        ind += 1
    
t = input()
p = input()
rolliha(t, p)
