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 main():
    import sys
    input = sys.stdin.readline

    class RollingHash:
        def __init__(self, S, base, mod):
            self.S = S
            self.mod = mod
            self._hash = [0] * (len(S) + 1)
            self.pow = [1] * (len(S) + 1)

            for i, s in enumerate(S):
                self._hash[i + 1] = (self._hash[i] * base + s) % mod
                self.pow[i + 1] = (self.pow[i] * base) % mod

        def get(self, l, r):
            # 0-indexed, [l. r)
            return (self._hash[r] - self._hash[l] * self.pow[r - l]) % self.mod

    S = [ord(s) for s in input().rstrip('\n')]
    T = [ord(t) for t in input().rstrip('\n')]

    RH_S = RollingHash(S, 1007, 1000000007)
    RH_T = RollingHash(T, 1007, 1000000007)
    lt = len(T)
    T_hash = RH_T.get(0, lt)
    for i in range(len(S) - len(T) + 1):
        if RH_S.get(i, i+lt) == T_hash:
            print(i)


if __name__ == '__main__':
    main()

