E. Толин өрөө

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

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

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

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

Зарим нүднүүд нь битүү $n × m$ хэмжээтэй тор байна гэж бодъё. Торны зүүн дээд нүд $(1, 1)$ координаттай, баруун доод нүд $(n, m)$ координаттай байна. Мөн энэ торны $k$ ширхэг нүд нь битүү байх ба үлдсэн нүднүүд нь хоосон байна. Та $(x_{s}, y_{s})$ хоосон нүдний төвөөс диагоналийн (ташуу шугамны) дагуу аль нэг чигт (өөрөөр хэлбэл зүүн хойд, баруун хойд, зүүн өмнөд, баруун өмнөд ) лазерийн туяа тусгана. Хэрвээ лазерийн туяа битүү нүд юмуу торны ирмэгийг дайрвал туяа ойдог. Янз бүрийн нөхцөл байдалд туяа хэрхэн ойхыг доорх зурагт дүрсэлсэн байна.

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

Оролт

Оролтын эхний мөр нь $n$, $m$, $k$ $(1 ≤ n, m ≤ 10^{5}, 0 ≤ k ≤ 10^{5})$ гурван бүхэл тоог агуулна. Дараагийн $k$ мөр бүр нь $x_{i}$ ба $y_{i}$ $(1 ≤ x_{i} ≤ n, 1 ≤ y_{i} ≤ m)$ хоёр бүхэл тоог агуулна. Энэ нь $i$-р нүд битүү гэдгийг илтгэнэ.

Оролтын сүүлийн мөр нь $x_{s}$, $y_{s}$ $(1 ≤ x_{s} ≤ n, 1 ≤ y_{s} ≤ m)$ тоонууд болон туяаны чиглэлүүдийн ("NE", "NW", "SE", "SW") аль нэгийг агуулна. Эдгээр тэмдэгт мөрүүд нь $(-1, 1)$, $(-1, -1)$, $(1, 1)$, $(1, -1)$ чиглэлүүдийг илтгэнэ.

Битүү нүднүүд хоорондоо давхцахгүй байхаар өгөгдөнө.

Гаралт

Туяа дор хаяж нэг удаа өнгөрөх хоосон нүднүүдийн тоог нэг мөрөнд хэвлэнэ.

С++ хэлний оролт гаралтын хэлбэрт $\%lld$ буюу тодорхойлбол 64-bit бүхэл тоог бүү хэрэглээрэй. Харин $cin$, $cout$ урсгал эсвэл $\%I64d$ хэлбэрийг ашиглавал тохиромжтой.

Орчуулсан: Даариймаа

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

Оролт
3 3 0
1 2 SW
Гаралт
6
Оролт
7 5 3
3 3
4 3
5 3
2 1 SE
Гаралт
14
Сэтгэгдлүүдийг ачааллаж байна...