Вірус#157

Вірус

1 second
512 megabytes
Medium

Степан дуже ретельно слідкує за своїм здоров'ям. Кожного дня він читає книги з медицини і шукає інформацію про нові хвороби, тому вже давно знає, що різні хвороби можуть збуджуватись вірусами. Степану давно відомі деякі види вірусів і він перевірив, що жодного з них у нього не має.

Але одного не найвдалішого для Степана дня він дізнався, що віруси можуть мутувати після того, як потрапили в організм людини. Мутація – це зміна ДНК таким чином, що в ньому змінюються рівно 2 символи, відстань між якими дорівнює . ДНК віруса до потрапляння в організм людини представлено у вигляді рядка , який складається з маленьких літер латинського алфавіту.

Дізнавшись таку страшну новину, Степан одразу кинувся перевіряти, чи не хворіє він мутивованим вірусом. ДНК Степана також є рядком з маленьких літер латинського алфавіту. Допоможіть йому дізнатись, чи є в його ДНК підрядки довжиною , які підходять під опис мутивованого віруса, наведений вище.

Input

В першому рядку вхідного файлу дано представлення ДНК Степана - рядок з маленьких літер латинського алфавіту. У другому рядку задано представлення ДНК віруса - рядок з маленьких літер латинського алфавіту. В третьому рядку задано число k (1 \le k \le n-1).

Output

У перший рядок вихідного файлу виведіть скільки разів мутивований вірус зустрічається в ДНК Степана. У другому рядку виведіть через пробіл в зростаючому порядку індекси початку входження мутивованого вірусу.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

В даній задачі три підзадачі. Бали за кожну підзадачу нараховуються тільки якщо усі тести підзадачі пройдені.

Підзадача 1 (30 балів):

ДНК Степана і віруса складаються не більш чим із 100 символів.

Підзадача 2 (30 балів):

ДНК Степана і віруса складаються не більш чим із 10 000 символів.

Підзадача 3 (40 балів):

ДНК Степана і віруса складаються не більш чим із 200 000 символів.