D. Дамжуулагч

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Киберландын автомат нарийн боовны үйлдвэр (ABC) нь $n × m$ хүснэгт худалдаж авчээ. Үйлчлүүлэгчиддээ үйлчлэхийн тулд ABC хүснэгтэнд суудлууд бэлджээ. Суудал болгоны хэмжээ нь нэгж квадрадтай тэнцүү, тиймээс хүснэгтэнд нийт $2(n + m)$ ширхэг суудал байна.

ABC нь хүснэгтийн нэгж квадрат болгон дээр дамжуулагч байрлуулжээ. Энд нийт 3-н төрлийн дамжуулагч байгаа: "$^$", "$<$", "$>$". "$^$" дамжуулагч нь хоолыг дээш нь дамжуулна. "$<$" нь хоолыг зүүн зүгт, "$>$" нь хоолыг баруун зүгт дамжуулна.

Мөрийг дээрээс доошоо $1$-ээс $n$ хүртэл дугаарлая, баганыг зүүнээс баруун уруу $1$-ээс $m$ хүртэл дугаарлая. Бид хүснэгтийн мөрийн хамгийн дээд мөрийн дээд суудлыг $n+1$, хамгийн доод мөрийн доод суудлыг $0$ мөрөнд байрлаж байна гэж тооцно. Үүнтэй адилаар, баганын хамгийн баруун талын баруун суудлыг $m+1$, хамгийн зүүн талын мөрийн зүүн талд нь буй суудлыг $0$ багананд байна гэж тооцно. Одоогоор дамжуулагчийн чиглэлийн хязгаарлалтаас болоод үйлчлүүлэгч $n+1$ мөрөнд суух боломжгүй.

Өгөгдсөн анхны хүснэгтэнд нийт $q$ ширхэг үйл явц дарааллаараа болно. Энд 2 төрлийн үйл явц байна:

  • "$A$ $x$ $y$"-ийн утга нь нэг ширхэг талх $x$ мөрийн $y$ багананд бий болно (үүнээс хойш ийм байрлалыг $(x, y)$ гэж тэмдэглэнэ). Талх үйлчлүүлэгчийн сууж байгаа суудал дээр очих хүртлээ дамжуулагчуудаар дамжина. Талх нь хязгааргүй цикл орон гацах боломжтой. Таны даалгавар нь үйл явцыг хянан талхны эцсийн байрлалыг олох, эсвэл талх хязгааргүй циклд орох эсэхийг шалгах юм.
  • "$C$ $x$ $y$ $c$"-ийн утга нь $(x, y)$ байрлал дээр байгаа дамжуулагчийг $c$ дамжуулагч болгон өөрчилнө.

Талх нь хязгааргүй циклд гацсан байсан ч гэсэн үйл явц болгон тусдаа гүйцэтгэгдэнэ. Ингэсэнээр үйл явц нь дараагийн үйл явцууддаа нөлөөлөхгүй юм.

Оролт

Оролтын эхний мөрөнд 3-н бүхэл тоонууд $n$, $m$, $q$ ($1 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 10, 1 ≤ q ≤ 10^{5}$) зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн $n$ ширхэг мөрөнд хүснэгтийг тайлбарлах бөгөөд мөр болгон $m$ ширхэг тэмдэгт агуулна. Тэмдэгтүүд зөвхөн "$<$, $^$, $>$" эдгээрийн нэг байна.

Дараагийн $q$ ширхэг мөр болгонд үйл явц болгоны тайлбар өгөгдөнө. Тайлбар нь "$C x y c$" эсвэл "$A x y$" хэлбэрээр өгөгдөнө (Элемэнтүүд зайгаар тусгаарлагдсан байна). $1 ≤ x ≤ n, 1 ≤ y ≤ m$ байх нь баталгаатай. $c$ тэмдэгт нь "$<$, $^$, $>$" эдгээрийн нэг байна.

Энд "C" төрлийн үйл явцаас хамгийн ихдээ $10000$-н ширхэг байна.

Гаралт

"A" төрлийн үйл явц болгоны хувьд нэг мөрөнд 2 зайгаар тусгаарлагдсан бүхэл тоонууд $tx$, $ty$-ыг хэвлэнэ үү. $(tx, ty)$ нь $(x, y)$-ы эцсийн байрлал юм.

Хэрвээ хязгааргүй циклд гацах бол $tx = ty =  - 1$ гэж хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
2 2 3
>>
^^
A 2 1
C 1 2 <
A 2 1
Гаралт
1 3
-1 -1
Оролт
4 5 7
><<^<
^<^^>
>>>^>
>^>>^
A 3 1
A 2 2
C 1 4 <
A 3 1
C 1 2 ^
A 3 1
A 2 2
Гаралт
0 4
-1 -1
-1 -1
0 2
0 2

Тэмдэглэл

Эхний жишээний хувьд:

Хэрвээ талх $(2, 1)$-ээс эхэлбэл, $(1, 3)$ байрлалд очих буюу хүснэгтээс гарч явна.

$(1, 2)$ байрлалын дамжуулагчийг "$<$" болгож өөрчилсөний дараа, талх $(2, 1)$-ээс гарч "$><$" гэсэн хязгааргүй циклд гацна. Тиймээс $( - 1,  - 1)$ гэж хэвлэнэ.

Сэтгэгдлүүдийг ачааллаж байна...