Даша увлекается всякими сложными головоломками — кубик Рубика 3 × 3 × 3, 4 × 4 × 4, 5 × 5 × 5 и тому подобное. На этот раз у неё есть циклическая таблица размера n × m клеток из строчных букв латинского алфавита. Каждая клетка таблицы имеет координаты (i, j) (0 ≤ i < n, 0 ≤ j < m). Цикличность этой таблицы заключается в том, что правее клетки (i, j) находится клетка , а ниже находится клетка .

Также у Даши есть шаблон. Шаблоном является нециклическая таблица размера r × c клеток. Каждая клетка шаблона является либо строчной буквой латинского алфавита либо символом вопроса. Каждая клетка шаблона имеет координаты (i, j) (0 ≤ i < r, 0 ≤ j < c).

Задачей головоломки является определение всех позиций вхождения шаблона в циклическую таблицу.

Определим позицию вхождения шаблона в циклическую таблицу. Позиция (i, j) циклической таблицы является позицией вхождения, если для каждого (x, y), что 0 ≤ x < r и 0 ≤ y < c, выполняется одно из двух условий:

• Клетка шаблона с координатами (x, y) является символом вопроса.
• Клетка циклической таблицы с координатами равняется клетке шаблона с координатами (x, y).

Даша прекрасно справилась с решением этой головоломки, впрочем как и со всеми остальными головоломками. Посмотрим, сможете ли вы это сделать.