CSES - E4590 2017 6 - Matching
  • Time limit: 10.00 s
  • Memory limit: 512 MB

A search pattern is a string which can be searched in another string. A match in a string is a substring of the original string so that each character in the pattern matches each character in the substring in order. Two characters match if they are same or if the character in the pattern is ?.

Given two strings, pattern and text, find all positions in the text that match the given pattern.

Input

The first line contains a single string, the pattern.

The second line contains a single string, the text.

Output

First line should contain a single integer, the number of matches in the input.

Each next line should contain exactly one integer, the index of the start of the substring the pattern matches.

Limits

  • 1 \le |pattern| \le |text| \le 4\cdot10^5.
  • Each word consists of only English lower case letters a-z.

Example

Input:

a?b
aabb

Output:

2
1
2