Kazak Vus və cədvəl#10487
Kozak Vus yaxınlarda sətir və sütundan ibarət bir matrisi tapdı. Bu matrisi yalnız , , , simvolları təşkil edir.
Kozak Vus matrisdə hərəkət qaydalarını belə müəyyən etdi: Əgər siz hazırda hüceyrəsindəsinizsə (yəni -ci sətir və -ci sütunun kəsişdiyi nöqtədə), o zaman:
a_{i j}='<' olduqda, (x, y-1) hüceyrəsinə keçirsiniz;
a_{i j}='>' olduqda, (x, y+1) hüceyrəsinə keçirsiniz;
a_{i j}=\text{'v'} olduqda, (x+1, y) hüceyrəsinə keçirsiniz;
a_{i j}=\text{'\textasciicircum'} 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ə sayda x_s \ \ y_s \ \ x \ y \ c 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_{x y} elementini 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.
Birinci sətir iki tam ədəd və (1 \le n, m \le 1500) — sətir və sütunların sayını göstərir.
Növbəti sətirdə matrisin müvafiq sətirinin elementləri: a_{i 1}, a_{i 2}, \dots, a_{i m} boşluq olmadan verilir.
Sonrakı sətir bir tam ədəd (1 \le q \le 10^5) — sorğuların sayını göstərir.
Növbəti sətirdə sorğuların təsviri verilir.
Bu sətirlərdən hər biri 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'}\}) şəklində sorğu təqdim edir.
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ə 1
( bal): n, m \le 100, q \le 1000;
( bal): başlanğıcda matrisin hər bir hüceyrəsindən çıxmaq mümkün deyil;
( bal): n, m \le 300, başlanğıcda matrisin hər bir hüceyrəsindən çıxmaq mümkündür;
( bal): n, m \le 300;
( bal): başlanğıcda matrisin hər bir hüceyrəsindən çıxmaq mümkündür;
( bal): əlavə məhdudiyyətlər olmadan.