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
T = input()
P = input()


class RollingHash:
    def __init__(self, s):
        self.s = s
        self.n = len(s)
        self.hash1 = [0] * (self.n + 1)
        self.power1 = [1] * (self.n + 1)
        self.base1, self.mod1 = pow(2, 64) - 1, 10 ** 9 + 7

        self.construct()

    def construct(self):
        for i, c in enumerate(self.s):
            self.hash1[i + 1] = ((self.hash1[i] * self.base1) % self.mod1 + ord(c)) % self.mod1
            self.power1[i + 1] = (self.power1[i] * self.base1) % self.mod1

    # [l, r)
    def get_hash(self, l, r):
        res1 = (self.hash1[r] - (self.hash1[l] * self.power1[r - l] % self.mod1)) % self.mod1
        return [res1]


rh_t = RollingHash(T)
rh_p = RollingHash(P)
p_hash = rh_p.get_hash(0, len(P))
for i in range(len(T) - len(P) + 1):
    if rh_t.get_hash(i, i + len(P)) == p_hash:
        print(i)

