E. Хэлхээ

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

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

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

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

Бүх хүүхдүүдтэй адилаар Алеша шинэ жилийн баярт ихэд дуртай байжээ. Баярын үеэр Алеша болон түүний гэр бүл гацуур модоо чимэглэдэг байв. Бүх хүүхдүүдтэй адилаар Алеша хэлхээнүүдээр тоглох дуртай ажээ. Хэлхээ гэдэг нь гэрлийн шилнээс тогтох гинжин хэлхээг хэлнэ.

Алеша $n × m$ хэмжээ бүхий хүснэгтийг тоглохдоо ашиглана. Уг хүснэгтийн мөрүүд нь дээрээс доош хүртэл $1$-ээс $n$ хүртэл дугаарлагдсан байх бөгөөд баганууд нь зүүнээс баруун хүртэл $1$-ээс $m$ хүртэл дугаарлагдсан байх юм.

Алеша-д уг хүснэгтэд байрлуулах $k$ ширхэг хэлхээнүүд байжээ. Тэрээр хэлхээ болгоны гэрлийн шил болгон нь хүснэгтийн ямар нэгэн нүдний төвд байрлах бөгөөд хүснэгтийн нүд болгон нь хамгийн ихдээ нэг ширхэг гэрлийн шил агуулж байхаар хэлхээнүүдийг хүснэгтэд байрлуулах юм. Мэдээж хэрэг ямар нэгэн хэлхээнд байрлах зэргэлдээ гэрлийн шилнүүд нь ерөнхий талтай байх(өөрөөр хэлбэл талаараа хөрш гэсэн үг юм) нүднүүдэд байрласан байна.

Хэлхээг байрлуулах жишээг зурагт дүрслэв.

Хэлхээ болгон нь ямар нэгэн хугацааны мөчид асах эсвэл унтрах юм. Хэрэв ямар нэгэн хэлхээ нь асвал уг хэлхээнд байрлах гэрлийн шил болгон нь асах бөгөөд хэлхээ унтрах үед мөн л адил уг хэлхээний гэрлийн шил болгон нь унтарна. Нийт хэлхээнүүдийн олонлог доторх бүх гэрлийн шилнүүд нь ер бусын бөгөөд иймд эдгээр гэрлийн шилнүүд нь асахад Алеша-д ямар нэгэн бүхэл тоогоор илэрхийлэгдэх сэтгэл ханамжийг өгөх ажээ. Гэвч унтарсан байгаа гэрлийн шилнүүд нь Алеша-д ямар нэгэн сэтгэл ханамж өгөхгүй байх юм.

Алеша хэлхээнүүдийг асааж унтрааж чадах бөгөөд тэрээр хүснэгтийн ямар нэгэн тэгш өнцөгт хэлбэртэй хэсгийн нүднүүдийн төвд байрлах гэрлийн шилнүүд нь түүнд нийтдээ ямар хэмжээний сэтгэл ханамж өгөхийг мэдэхийг хүсжээ. Анхандаа бүх хэлхээнүүд нь асаалттай байх юм.

Алеша жаахан хүүхэд хэвээр байгаа бөгөөд том тоонуудыг хооронд нь нэмж чадахгүй ажээ. Иймд тэрээр танаас тусламж хүсжээ.

Оролт

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

Дараагийн мөрүүдэд хэлхээнүүдийн олонлогийн тайлбар дараах хэлбэрийн дагуу өгөгдөнө:

Нэг хэлхээний тайлбарын эхний мөрөнд бүхэл тоо $len$ ($1 ≤ len ≤ 2000$) өгөгдөх ба энэ нь уг хэлхээнд байрлах гэрлийн шилний тоог илэрхийлнэ.

Дараагийн $len$ ширхэг мөрийн мөр болгонд 3 бүхэл тоо $i$, $j$ болон $w$ ($1 ≤ i ≤ n$, $1 ≤ j ≤ m$, $1 ≤ w ≤ 10^{9}$) өгөгдөх ба эдгээр нь гэрлийн шил агуулж буй нүдний координатууд болон уг гэрлийн шил асах үед Алеша-ын авах сэтгэл ханамжийн хэмжээг илэрхийлнэ. Гэрлийн шилнүүд нь хэлхээн доторх гинжин хэлхээг үүсгэж буй дарааллынхаа дагуу оролтод өгөгдөх бөгөөд хөрш гэрлийн шилнүүд нь ерөнхий талтай нүднүүдэд байрласан байна.

Дараагийн мөрөнд бүхэл тоо $q$ ($1 ≤ q ≤ 10^{6}$) өгөгдөх ба энэ нь Алеша-ын тоглоомын үйл явдлын тоог илэрхийлнэ. Дараагийн $q$ ширхэг мөрөнд эдгээр үйл явдлуудыг цаг хугацааны дарааллаар нь дүрсэлнэ. Эдгээрийн $i$-дахь мөрөнд $i$-дахь үйл явдлыг дүрслэх бөгөөд дараах хэлбэрүүдийн аль нэг хэлбэрээр өгөгдсөн байх юм:

  • SWITCH $i$ -- Алеша хэрэв $i$-р хэлхээ нь асаалттай байвал унтраах бөгөөд хэрэв $i$-р хэлхээ нь унтарсан байвал асаах юм. Мөн $1 ≤ i ≤ k$ байна.
  • ASK $x_{1}$ $y_{1}$ $x_{2}$ $y_{2}$ -- Алеша хүснэгтийн нэгэн тэгш өнцөгт хэлбэртэй хэсэгт байрлах гэрлийн шилнүүдийн түүнд өгөх нийт сэтгэл ханамжийн хэмжээг мэдэхийг хүсжээ. Уг хэсгийн зүүн дээд нүд нь $(x_{1}, y_{1})$ гэсэн координаттай байх бөгөөд баруун доод нүд нь $(x_{2}, y_{2})$ гэсэн координаттай байх юм. Мөн $1 ≤ x_{1} ≤ x_{2} ≤ n$ байх ба $1 ≤ y_{1} ≤ y_{2} ≤ m$ байна. Уг төрлийн үйл явдал нь оролтод $2000$-оос олон удаа өгөгдөхгүй байхыг анхаарна уу.

Оролтод өгөгдөх бүх тоонууд нь бүхэл тоонууд байна.

Оролт нь маш том байх бөгөөд иймд ямар нэгэн оролт хүлээн авах арга хэрэглэхдээ болгоомжтой байна уу. Тодруулбал C++ дээр cin in кодуудыг хэрэглэх нь тохиромжгүй байх бөгөөд Java дээр class Scanner in кодуудыг хэрэглэх нь мөн тохиромжгүй байна.

Гаралт

ASK гэсэн үйл явдал бүрийн хувьд Алеша-ын мэдэхийг хүссэн нийт утгын хэмжээг тусдаа мөрнүүдэд хэвлэнэ үү. Хариултуудыг цаг хугацааны дарааллаар хэвлэнэ үү.

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

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

Оролт
4 4 3
5
1 1 2
1 2 3
2 2 1
2 1 4
3 1 7
4
1 3 1
2 3 3
2 4 3
1 4 1
7
4 1 1
4 2 9
3 2 8
3 3 3
4 3 4
4 4 1
3 4 1
2
ASK 2 2 3 3
ASK 1 1 4 4
Гаралт
15
52
Оролт
4 4 1
8
4 1 1
3 1 2
2 1 1
1 1 7
1 2 5
2 2 4
2 3 1
1 3 1
3
ASK 1 1 3 2
SWITCH 1
ASK 1 1 3 2
Гаралт
19
0

Тэмдэглэл

Уг зурагт эхний жишээг дүрсэлсэн байна.

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