593E орчуулах · Codeforces.mn

# Хачин тооцоолол ба муурнууд
Гошагийн ертөнц бол $n$ мөр $m$ баганаас бүрдэх хүснэгт юм. Мөр баганууд $1$-с эхлэн бүхэл тоогоор дугаарлагдсан. Бид $r$ мөр болон $c$ баганад байрласан нүдийг $(r, c)$ гэж тэмдэглэнэ.

Гоша ихэвчлэн хаа нэгтээ уригддаг. Тэр урилга авах бүртээ эхлээд уг газарт очих замуудын тоог тооцоолдог ба тэгээд очдог. Гошагийн байшин $(1, 1)$ нүдэнд байдаг.

Хугацааны дурын мөчид Гоша одоо байгаа нүднээсээ хөрш нүдрүү хөдлөнө (хоёр нүд нь ижил талтай бол хөрш болно). Мэдээж хөдлөх гэж буй нүд оршин байгаа үед л хөдөлгөөнийг хийж болно, өөрөөр Гоша хүснэгтийн хүрээнээс давж явахгүй гэсэн үг. Иймээс тэр $(r, c)$ нүднээс $(r - 1, c)$, $(r, c - 1)$, $(r + 1, c)$, $(r, c + 1)$ нүднүүдийн аль нэгрүү л хөдлөж чадна. Мөн Гоша үйлдлийг алгасаж болох ба одоо байгаа $(r, c)$ нүдэндээ үлдэж болно.

Хачин тооцоололд дуртайгаас гадна Гоша муурны харшилтай ба тэр хэзээ ч дотроо мууртай нүдрүү явахгүй. Гоша яг хэзээ, хаана уригдахаа мэдэж байгаа мөн муурнуудын хүснэгтэн дээрх аяллын хуваарийг мэдэж байгаа. Дэлгэрэнгүй хэлбэл түүнд $q$ бичлэг байгаа ба эдгээрийн $i$-р бичлэг нь дараах хэлбэрүүдээс аль нэг хэлбэртэй байна:

* $1$, $x\_{i}$, $y\_{i}$, $t\_{i}$ нь Гоша хугацааны $t\_{i}$ мөчид $(x\_{i}, y\_{i})$ нүдэнд очихоор уригдсан гэсэн үг. Мэдээж $(x\_{i}, y\_{i})$ нүдэнд тухайн цагт муур байхгүй байна.
  * $2$, $x\_{i}$, $y\_{i}$, $t\_{i}$ нь хугацааны $t\_{i}$ мөчид $(x\_{i}, y\_{i})$ нүдэнд муур байна гэсэн үг. Мэдээж $(x\_{i}, y\_{i})$ нүдэнд тухайн цагт өөр муур байхгүй байна.
  * $3$, $x\_{i}$, $y\_{i}$, $t\_{i}$ нь хугацааны $t\_{i}$ мөчид муур $(x\_{i}, y\_{i})$ нүднээс гарна гэсэн үг. Мэдээж $(x\_{i}, y\_{i})$ нүдэнд байрласан муур байх нь тодорхой.

Гоша нэг л урилгыг зөвшөөрөхөөр төлөвлөж байгаа боловч тэр хараахан яг аль нь вэ гэдгийг шийдээгүй байна. Шийдвэрээ гаргахын тулд тэр таныг $i$ урилга бүрийн хувьд хугацааны $t\_{i}$ мөчид $(x\_{i}, y\_{i})$ нүдэнд очих замуудын тоог тооцоолохыг хүсч байна. Урилга бүрийн хувьд Гоша хугацааны $1$ мөчид $(1, 1)$ нүднээс хөдлөж эхэлнэ гэж үзээрэй.

Гоша хоёр хөрш нүдний хооронд шилжихдээ нэгж хугацаа зарцуулна. Энэ нь Гоша зөвхөн хэрвээ уг нүдэнд байгаа муур Гошаг хөрш нүхнээс хөдөлгөөнөө эхлэхээс өмнө нүдийг сулласан байвал л очиж чадна гэсэн үг. Мөн Гошаг уг нүдэнд байх хугацаанд ямар ч муур ирэхгүй тохиолдолд очиж чадна.

$(1, 1)$ нүднээс $(x, y)$ нүдэнд хугацааны $t$ мөчид очих хоёр зам нь хэрвээ $1$-c $t$ хүртэлх хугацаанд ядаж нэг мөчид Гошагийн байрлал хоёр зам дээр ялгаатай байвал уг хоёр зам нь ялгаатайд тооцогдоно. Уг аяллын туршид Гоша $(1, 1)$ болон $(x, y)$ нүднүүдэд хэдэн ч удаа очиж болно. Явж болох замуудын тоо их байж болох учир $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэ.

## Оролт
Оролтын эхний мөрөнд гурван эерэг бүхэл тоо $n$, $m$ ба $q$ ($1 ≤ n\*m ≤ 20, 1 ≤ q ≤ 10 000$) байх ба харгалзан хүснэгтийн мөр болон баганын тоо ба үйл явдлуудын тоо байна.

Дараагийн $q$ мөрөнд үйл явдлуудыг тодорхойлох ба тодорхойлолт бүр дөрвөн бүхэл тоон утга $tp\_{i}$, $x\_{i}$, $y\_{i}$ ба $t\_{i}$ ($1 ≤ tp ≤ 3, 1 ≤ x ≤ n, 1 ≤ y ≤ m, 2 ≤ t ≤ 10^{9}$) агуулах ба харгалзан үйл явдлын төрөл, үйл явдал тохиох нүдний координат болон үйл явдал тохиох хугацааны агшин байна.

Бичлэгүүд нь цаг хугацааны хувьд эрэмбэлэгдсэн байх ба өөрөөр $t\_{i} < t\_{i + 1}$ байна.

## Гаралт
$i$ Урилга бүрийн хувьд $(x\_{i}, y\_{i})$ нүдэнд хугацааны $t\_{i}$ мөчид очих замуудын тоог тооцоолж хэвлэнэ. Хариултуудыг оролтонд өгөгдсөн дарааллаар хэвлэ.

## Тэмдэглэл
Эхний жишээний тайлбар. Зураг бүр нүдэнд тухайн хугацаанд очих замуудын тоог тодорхойлно. (X нь хугацааны тухайн агшинд нүд хаагдсан байгааг илэрхийлнэ)

![](http://codeforces.com/predownloaded/b7/eb/b7eb951aaa9bad30b91c27f2c6bca2e1a08fc8d9.png) Хугацааны агшин 1.  ![](http://codeforces.com/predownloaded/fd/d7/fdd775eb387b127877577b176d072005e092f745.png) Хугацааны агшин 2. ![](http://codeforces.com/predownloaded/31/dc/31dc2061d35b313ddef7d34bd62b8ffb3f04cd13.png) Хугацааны агшин 3. ![](http://codeforces.com/predownloaded/31/dc/31dc2061d35b313ddef7d34bd62b8ffb3f04cd13.png) Хугацааны агшин 4. ![](http://codeforces.com/predownloaded/04/4f/044f712a6cdee3e3acd3da8c6757c18ca3c20717.png) Хугацааны агшин 5. ![](http://codeforces.com/predownloaded/b6/7e/b67e77d4a45b7222bb0997e525a7a843852bf6a6.png) Хугацааны агшин 6. ![](http://codeforces.com/predownloaded/67/bf/67bf98d33c6bf6dd7d1c826316c4eded50580e4c.png) Хугацааны агшин 7.

-- Г.Мэндбаяр

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

Оролт

Гаралт

Оролт

Гаралт

2
42

Оролт

Гаралт

490902
10598759