B. Сансрын хүснэгтүүд

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

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

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

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

The Free Meteor Association (FMA)-д нэгэн асуудал үүсжээ: Солирууд хөдөлж байгаа бөгөөд Universal Cosmic Descriptive Humorous Program (UCDHP) уг хөдөлгөөнийг шинжлэх тусгай хэсэг гаргах хэрэгтэй байгаа юм.

UCDHP нь өөрийн нүднүүддээ бүхэл тоо агуулсан $n × m$ хүснэгт хэлбэртэй эдгээр солируудын талаар нууц мэдээлэл хадгалж байв. Огторгуйд байгаа эдгээр солируудын дараалал нь өөрчлөгдөж байгаа бөгөөд ийм учраас UCDHP-ын үндсэн хэсэг дараах асуултуудыг хүлээн авчээ:

  • хүснэгтийн 2 мөрийг солих асуулт;
  • хүснэгтийн 2 баганыг солих асуулт;
  • Хүснэгтийн тодорхой нэг нүдэнд байх нууц дугаарыг олох асуулт.

UCDHP-ын үндсэн хэсэг нь маш их ноцтой байдалд байгаа учраас уг хүснэгттэй ажиллах функционалыг бичүүлэхээр таныг томилжээ.

Оролт

Эхний мөрөнд харгалзан хүснэгтийн мөр, баганын тоо болон асуултуудын тоог илэрхийлэх зайгаар тусгаарлагдсан 3 бүхэл тоо $n$, $m$ болон $k$ ($1 ≤ n, m ≤ 1000$, $1 ≤ k ≤ 500000$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг зайгаар тусгаарлагдсан тоонууд өгөгдөнө. Эдгээр нь хүснэгтийн анхны бүтцийг илэрхийлнэ. Хүснэгтэд байх $p$ тоо бүр нь бүхэл тоо байх ба $0 ≤ p ≤ 10^{6}$ тэнцэтгэл бишийг хангасан байна.

Дараагийн $k$ мөрөнд асуултууд нь "$s_{i}$ $x_{i}$ $y_{i}$" хэлбэртэйгээр өгөгдөх ба энд $s_{i}$ нь "$с$", "$r$" эсвэл "$g$" гэсэн тэмдэгт байх ба $x_{i}$, $y_{i}$ нь бүхэл тоонууд байна.

  • Хэрэв $s_{i}$ = "$c$" байвал уг асуулт нь $x_{i}$ болон $y_{i}$ ($1 ≤ x, y ≤ m, x ≠ y$) дугаартай багануудыг солих асуулт байна;
  • Хэрэв $s_{i}$ = "$r$" байвал уг асуулт нь $x_{i}$ болон $y_{i}$ ($1 ≤ x, y ≤ n, x ≠ y$) дугаартай мөрүүдийг солих асуулт байна;
  • Хэрэв $s_{i}$ = "$g$" байвал уг асуулт нь $x_{i}$-дахь мөр болон $y_{i}$-дахь баганад байрлалтай тоог олох асуулт байна ($1 ≤ x ≤ n, 1 ≤ y ≤ m$).

Хүснэгтийн мөрнүүд нь дээрээсээ доош хүртэл 1-ээс $n$ хүртэл дугаарлагдсан ба баганууд нь зүүнээсээ баруун хүртэл 1-ээс $m$ хүртэл дугаарлагдсан байна.

Гаралт

Тоо олох асуулт бүрийн хувьд ($s_{i}$ = "$g$") шаардагдсан тоог хэвлэнэ үү. Асуултуудын хариултыг оролтод өгөгдсөн дарааллаар нь хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
3 3 5
1 2 3
4 5 6
7 8 9
g 3 2
r 3 2
c 2 3
g 2 2
g 3 2
Гаралт
8
9
6
Оролт
2 3 3
1 2 4
3 1 5
c 2 1
r 1 2
g 1 3
Гаралт
5

Тэмдэглэл

2-дахь жишээнд хүснэгт нь хэрхэн өөрчлөгдөхийг харцгаая.

Эхний үйлдлийг хийсний дараа хүснэгт нь дараах байдалтай харагдана:

2 1 4

1 3 5

2-дахь үйлдлийг хийсний дараа хүснэгт нь дараах байдалтай харагдана:

1 3 5

2 1 4

Иймд 3-дахь асуултын хариулт нь 1-р мөр болон 3-р баганад байрлалтай тоо буюу 5 байх юм.

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