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
class RollingHash:
    def __init__(self, S):
        N = len(S)
        self.N = N
        self.base1 = 1007
        self.mod1 = 10**9 + 7
        self.hash1 = [0] * (N+1)
        self.power1 = [1] * (N+1)

        for i, e in enumerate(S):
            self.hash1[i+1] = (self.hash1[i] * self.base1 + ord(e)) % self.mod1
            self.power1[i+1] = (self.power1[i] * self.base1) % self.mod1
    
    def get(self, lv, rv):
        return (self.hash1[rv] - self.hash1[lv] * self.power1[rv-lv] % self.mod1) % self.mod1

S = input()
T = input()
rh_s = RollingHash(S)
rh_t = RollingHash(T)
ns = len(S)
nt = len(T)

for i in range(ns - nt+1):
    if rh_t.get(0,nt) == rh_s.get(i, i+nt):
        print(i)




    
