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
alp = "abcdefghijklmnopqrstuvwxyz0123456789"
dic = {}

for i in range(36):
    dic[alp[i]] = i


P = input()
T = input()

if len(P) < len(T):
    sys.exit()

Thash1 = 0
Thash2 = 0
mod1 = 10**9+7
mod2 = 10**9+9

suc1 = pow(36,len(T),mod1)
suc2 = pow(36,len(T),mod2)


for i in T:

    Thash1 *= 36
    Thash2 *= 36

    Thash1 += dic[i]
    Thash2 += dic[i]
    Thash1 %= mod1
    Thash2 %= mod2

Phash1 = 0
Phash2 = 0

for i in range(len(T)):

    Phash1 *= 36
    Phash2 *= 36

    Phash1 += dic[P[i]]
    Phash2 += dic[P[i]]
    Phash1 %= mod1
    Phash2 %= mod2

for i in range(len(P)-len(T)+1):

    if Thash1 == Phash1 and Thash2 == Phash2:
        print (i)

    if i != len(P)-len(T):
        Phash1 *= 36
        Phash2 *= 36

        Phash1 -= suc1 * dic[P[i]]
        Phash2 -= suc2 * dic[P[i]]

        Phash1 += dic[P[i+len(T)]]
        Phash2 += dic[P[i+len(T)]]
        Phash1 %= mod1
        Phash2 %= mod2
