Степан дуже ретельно слідкує за своїм здоров'ям. Кожного дня він читає книги з медицини і шукає інформацію про нові хвороби, тому вже давно знає, що різні хвороби можуть збуджуватись вірусами. Степану давно відомі деякі види вірусів і він перевірив, що жодного з них у нього не має.
Але одного не найвдалішого для Степана дня він дізнався, що віруси можуть мутувати після того, як потрапили в організм людини. Мутація – це зміна ДНК таким чином, що в ньому змінюються рівно 2 символи, відстань між якими дорівнює . ДНК віруса до потрапляння в організм людини представлено у вигляді рядка , який складається з маленьких літер латинського алфавіту.
Дізнавшись таку страшну новину, Степан одразу кинувся перевіряти, чи не хворіє він мутивованим вірусом. ДНК Степана також є рядком з маленьких літер латинського алфавіту. Допоможіть йому дізнатись, чи є в його ДНК підрядки довжиною , які підходять під опис мутивованого віруса, наведений вище.
В першому рядку вхідного файлу дано представлення ДНК Степана - рядок з маленьких літер латинського алфавіту. У другому рядку задано представлення ДНК віруса - рядок з маленьких літер латинського алфавіту. В третьому рядку задано число k (1 \le k \le n-1).
У перший рядок вихідного файлу виведіть скільки разів мутивований вірус зустрічається в ДНК Степана. У другому рядку виведіть через пробіл в зростаючому порядку індекси початку входження мутивованого вірусу.
Приклад 1
Приклад 2
В даній задачі три підзадачі. Бали за кожну підзадачу нараховуються тільки якщо усі тести підзадачі пройдені.
Підзадача 1 (30 балів):
ДНК Степана і віруса складаються не більш чим із 100 символів.
Підзадача 2 (30 балів):
ДНК Степана і віруса складаються не більш чим із 10 000 символів.
Підзадача 3 (40 балів):
ДНК Степана і віруса складаються не більш чим із 200 000 символів.