Kazak Vus və cədvəl

Kozak Vus yaxınlarda $n$ sətir və $m$ sütundan ibarət bir $a$ matrisi tapdı. Bu matrisi yalnız $\text{’<’}$, $\text{’>’}$, $\text{’^’}$, $\text{’v’}$ simvolları təşkil edir.

Kozak Vus matrisdə hərəkət qaydalarını belə müəyyən etdi: Əgər siz hazırda $(x,y)$ hüceyrəsindəsinizsə (yəni $x$-ci sətir və $y$-ci sütunun kəsişdiyi nöqtədə), o zaman:

• $a_{ij}{=}^{\prime }{<}^{\prime }$ olduqda, $(x,y-1)$ hüceyrəsinə keçirsiniz;

• $a_{ij}{=}^{\prime }{>}^{\prime }$ olduqda, $(x,y+1)$ hüceyrəsinə keçirsiniz;

• $a_{ij}=\text{’v’}$ olduqda, $(x+1,y)$ hüceyrəsinə keçirsiniz;

• $a_{ij}=\text{’^’}$ olduqda, $(x-1,y)$ hüceyrəsinə keçirsiniz.

Yol yalnız matrisdən kənara çıxdığınız zaman sona çatır.

Kozak Vus sizə $q$ sayda $x_s{y}_{s}xyc$ tipli sorğular hazırlayıb. O, matrisdən kənara çıxmaq üçün keçməli olduğunuz hüceyrələrin sayını öyrənmək istəyir, əgər yolunuza $(x_s,y_s)$ hüceyrəsindən başlasanız. Bundan əlavə, o, yolun başlanğıcında $a_{xy}$ elementini $c$ ilə dəyişdirmək istəyir.

Qeyd edək ki, bu sorğular müstəqildir. Yəni, bir elementi müəyyən bir simvola dəyişdirsəniz, növbəti sorğudan əvvəl bu simvol əvvəlki vəziyyətinə qayıdır.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ və $m$ ($1\le n,m\le 1500$) — sətir və sütunların sayını göstərir.

Növbəti $n$ sətirdə matrisin müvafiq sətirinin elementləri: $a_{i1},a_{i2},\dots ,a_{im}$ boşluq olmadan verilir.

Sonrakı sətir bir tam ədəd $q$ ($1\le q\le 10^5$) — sorğuların sayını göstərir.

Növbəti $q$ sətirdə sorğuların təsviri verilir.

Bu sətirlərdən hər biri $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’}\}$) şəklində sorğu təqdim edir.

Çıxış verilənləri

Hər bir sorğu üçün ayrıca sətirdə matrisdən kənara çıxmaq üçün keçməli olduğunuz hüceyrələrin sayını göstərən bir tam ədəd çıxarın. Əgər siz heç vaxt matrisdən kənara çıxmayacaqsınızsa, «0» çıxarın.

Nümunələr

Qiymətləndirmə

1. ($13$ bal): $n,m\le 100,q\le 1000$;

2. ($13$ bal): başlanğıcda matrisin hər bir hüceyrəsindən çıxmaq mümkün deyil;

3. ($18$ bal): $n,m\le 300$, başlanğıcda matrisin hər bir hüceyrəsindən çıxmaq mümkündür;

4. ($12$ bal): $n,m\le 300$;

5. ($30$ bal): başlanğıcda matrisin hər bir hüceyrəsindən çıxmaq mümkündür;

6. ($14$ bal): əlavə məhdudiyyətlər olmadan.