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
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B&lang=jp
#  String Search : python3
#  2018.11.26 yonezawa

import sys
input = sys.stdin.readline
#import cProfile

def main():
    s1  = str(input()).rstrip('\n')
    s2  = str(input()).rstrip('\n')
    
    s1_len = len(s1)
    s2_len = len(s2)
    sc = 1
    for k in range(1,len(s2)):
        if s2[0] != s2[k]:
            break
        sc += 1
    tc = len(set(s2))

    if (tc == 1 and s2_len > 1):
        cnt = 0
        for k in range(s1_len ):
            if (s1[k] == s2[0]):
                cnt += 1
            else:
                cnt = 0
            if (cnt >= s2_len ):
                print (cnt - s2_len)
    else:
        i = s1.find(s2)
        while i != -1 :
            print (i)
            i = s1.find(s2,i+1)


if __name__ == '__main__':
    main()
    #pr = cProfile.Profile()
    #pr.runcall(main)
    #pr.print_stats()

