\begin{tutorial}{Прямоугольная квартира}

\begin{center}
\textit{Автор задачи и разработчик: Алексей Михненко}
\end{center}

Сначала предположим, что квартира черепашки бесконечна и не содержит мебели. Рассмотрим, какие клетки посетит черепашка, если начнёт свой путь из клетки $(1, 1)$. Если черепашка в итоге сдвинется направо больше, чем на $m$, то ответ на задачу $0$. Иначе, для каждого $y$ от $1$ до $m$ нетрудно видеть, что черепашка, либо не посетит ни одной клетки в столбце $y$, либо посетит отрезок клеток $[l_y, r_y]$: то есть все клетки $(x, y)$, где $l_y \le x \le r_y$.

Величины $l_y$ и $r_y$ можно посчитать заранее за $\mathcal{O}(|s|)$. С помощью этих величин уже нетрудно за $\mathcal{O}(m)$ для фиксированной клетки $(i, j)$ проверить, что она подходит под условие задачи:
\begin{itemize}
\item Для каждого $y$ от $1$ до $m$, если отрезок $[l_y, r_y]$ не пустой, надо убедится, что $j + y - 1 \le m$, а так же, что все клетки в этом столбце на отрезке $[i + l_y - 1, i + r_y - 1]$ существуют и не заняты мебелью.
\end{itemize}

Чтобы для каждого столбца осуществлять эту проверку эффективно, достаточно в каждом столбце насчитать префиксные суммы. Такой способ позволит проверять фиксированную клетку за $\mathcal{O}(m)$, что даёт решение за $\mathcal{O}(|s| + nm^2)$, если сделать проверку для каждой клетки независимо. Этого решения достаточно, чтобы сдать задачу на полный балл.

Данная задача также решается за $\mathcal{O}(|s| + nm\log(nm))$ с помощью перемножения двумерного многочленов, но это не требовалось.

\end{tutorial}
