Məsələlər
Козак Вус та таблиця
Козак Вус та таблиця
Козак Вус нещодавно знайшов таблицю $a$ з $n$ рядками та $m$ стовпчиками. При чому матриця складається лише з символів $\text{'<'}$, $\text{'>'}$, $\text{'\textasciicircum'}$, $\text{'v'}$.
Козак Вус встановив правила переміщення по матриці. Нехай зараз ви знаходитеся у клітинці $(x, y)$ (у клітинці на перетині $x$-го рядка та $y$-го стовпчика). Тоді, якщо
\begin{itemize}
\item $a_{i j}='<'$, то ви переміщуєтеся у клітинку $(x, y-1)$;
\item $a_{i j}='>'$, то ви переміщуєтеся у клітинку $(x, y+1)$;
\item $a_{i j}=\text{'v'}$, то ви переміщуєтеся у клітинку $(x+1, y)$;
\item $a_{i j}=\text{'\textasciicircum'}$, то ви переміщуєтеся у клітинку $(x-1, y)$.
\end{itemize}
Цей шлях закінчується лише тоді, коли ви вийдете за межі матриці.
Козак Вус підготував для вас $q$ запитів виду $x_s \ \ y_s \ \ x \ y \ c$. Козаку Вусу цікаво дізнатися кількість клітинок, які треба пройти, щоб вийти за межі матриці, якщо ви почнете свій шлях у клітинці $(xs, ys)$. При цьому, щоб ускладнити задачу, він хоче, щоб перед початком шляху змінити елемент $a_{x y}$ на $c$.
Зверніть увагу, що ці запити \textbf{незалежні}. Тобто, якщо ви змінили елемент на певний символ, то перед наступним запитом, цей символ стає таким, яким був.
\InputFile
Перший рядок містить два цілі числа $n$ та $m$ ($1 \le n, m \le 1500$)~--- кількість рядків та стовпчиків відповідно.
У наступних $n$ рядках містяться елементи відповідного рядка матриці: $a_{i 1}, a_{i 2}, \dots, a_{i m}$ без розділових пробілів.
Наступний рядок містить одне ціле число $q$ ($1 \le q \le 10^5$)~--- кількість запитів.
У наступних $q$ рядках міститься опис запитів.
У $i$-ому з цих рядків міститься запит у вигляді $x_s \ \ y_s \ \ x \ y \ c$ ($1 \le x_s, x, \le n, 1 \le y_s, y \le m, c \in \{\text{'<'}, \text{'>'}, \text{'\textasciicircum'}, \text{'v'}\}$).
\OutputFile
Для кожного запиту виведіть в окремому рядку єдине ціле число --- кількість клітинок, які треба пройти, щоб вийти за межі матриці, якщо ви почнете свій шлях у клітинці $(x_s, y_s)$. Якщо ви ніколи не вийдете за межі таблиці, то виведіть <<\t{0}>>.
\Scoring
\begin{enumerate}
\item ($13$ балів): $n, m \le 100, q \le 1000$;
\item ($13$ балів): початково з кожної клітинки матриці \textbf{не} можна вийти за межі;
\item ($18$ балів): $n, m \le 300$, початково з кожної клітинки матриці можна вийти за межі;
\item ($12$ балів): $n, m \le 300$;
\item ($30$ балів): початково з кожної клітинки матриці можна вийти за межі;
\item ($14$ балів): без додаткових обмежень.
\end{enumerate}
Giriş verilənləri #1
3 4 >>v> ><v> ^>>^ 4 2 1 1 1 ^ 2 1 2 2 > 2 1 2 1 < 1 1 2 4 ^
Çıxış verilənləri #1
0 6 1 8