Козак Вус нещодавно знайшов таблицю $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}