e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

Козак Вус та таблиця

Козак Вус нещодавно знайшов таблицю $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}
Time limit 1.5 second
Memory limit 512 MiB
Input example #1
3 4
>>v>
><v>
^>>^
4
2 1 1 1 ^
2 1 2 2 >
2 1 2 1 <
1 1 2 4 ^
Output example #1
0
6
1
8
Author Kostya Denisov