CSES - Aalto Competitive Programming 2024 - wk9 - Wed - Ctrl-F
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Maija has created herself a text editor that she has nicked Vimm - Vim improved. Now she needs a way to implement the Ctrl-F functionality: find all strings that match the searched string. As a part of this program she will write a function that returns all the positions where string a occurs in string b. Position 1 is the first character of b.

Input

A single line contains two string a and b, separated by space.

Output

First print the number of positions and then in the next line print the positions where and occurrence of string a starts in string b in increasing order. The strings are 1-indexed.

Constraints

  • 1 \leq |a| \leq |b| \leq 2 \times 10^5
  • a and b consist of lowercase Latin letters.

Example 1

Input:

bbb babbabbbbb

Output:

3
6 7 8

Example 2

Input:

l uilzslziog

Output:

2
3 6