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

Козак Вус нещодавно знайшов таблицю $a$ з $n$ рядками та $m$ стовпчиками. При чому матриця складається лише з символів $\text{’<’}$, $\text{’>’}$, $\text{’^’}$, $\text{’v’}$.

Козак Вус встановив правила переміщення по матриці. Нехай зараз ви знаходитеся у клітинці $(x,y)$ (у клітинці на перетині $x$-го рядка та $y$-го стовпчика). Тоді, якщо

• $a_{ij}{=}^{\prime }{<}^{\prime }$, то ви переміщуєтеся у клітинку $(x,y-1)$;

• $a_{ij}{=}^{\prime }{>}^{\prime }$, то ви переміщуєтеся у клітинку $(x,y+1)$;

• $a_{ij}=\text{’v’}$, то ви переміщуєтеся у клітинку $(x+1,y)$;

• $a_{ij}=\text{’^’}$, то ви переміщуєтеся у клітинку $(x-1,y)$.

Цей шлях закінчується лише тоді, коли ви вийдете за межі матриці.

Козак Вус підготував для вас $q$ запитів виду $x_s{y}_{s}xyc$. Козаку Вусу цікаво дізнатися кількість клітинок, які треба пройти, щоб вийти за межі матриці, якщо ви почнете свій шлях у клітинці $(xs,ys)$. При цьому, щоб ускладнити задачу, він хоче, щоб перед початком шляху змінити елемент $a_{xy}$ на $c$.

Зверніть увагу, що ці запити незалежні. Тобто, якщо ви змінили елемент на певний символ, то перед наступним запитом, цей символ стає таким, яким був.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $m$ ($1\le n,m\le 1500$) — кількість рядків та стовпчиків відповідно.

У наступних $n$ рядках містяться елементи відповідного рядка матриці: $a_{i1},a_{i2},\dots ,a_{im}$ без розділових пробілів.

Наступний рядок містить одне ціле число $q$ ($1\le q\le 10^5$) — кількість запитів.

У наступних $q$ рядках міститься опис запитів.

У $i$-ому з цих рядків міститься запит у вигляді $x_s{y}_{s}xyc$ ($1\le x_s,x,\le n,1\le y_s,y\le m,c\in \{\text{’<’},\text{’>’},\text{’^’},\text{’v’}\}$).

Вихідні дані

Для кожного запиту виведіть в окремому рядку єдине ціле число — кількість клітинок, які треба пройти, щоб вийти за межі матриці, якщо ви почнете свій шлях у клітинці $(x_s,y_s)$. Якщо ви ніколи не вийдете за межі таблиці, то виведіть «0».

Приклади

Оцінювання

1. ($13$ балів): $n,m\le 100,q\le 1000$;

2. ($13$ балів): початково з кожної клітинки матриці не можна вийти за межі;

3. ($18$ балів): $n,m\le 300$, початково з кожної клітинки матриці можна вийти за межі;

4. ($12$ балів): $n,m\le 300$;

5. ($30$ балів): початково з кожної клітинки матриці можна вийти за межі;

6. ($14$ балів): без додаткових обмежень.