Кунай#3386

Кунай

10 секунд

256 мегабайтів

Середня

Кунай — це зброя у формі ножа, яку використовують ніндзя. Ніндзя атакують ворога, кидаючи в нього кунай.

На сітці розміром $w$ стовпців і $h$ рядків розташовано $n$ ніндзя. Кожен ніндзя знаходиться в центрі своєї клітинки, і жодні два ніндзя не займають одну й ту саму клітинку. У кожного ніндзя є кунай, і кожен дивиться в одному з чотирьох напрямків: вгору, вниз, вліво або вправо. У момент часу $0$ кожен ніндзя кидає свій кунай у напрямку, в якому він дивиться.

Кожен кунай летить прямо зі швидкістю $1$ . Якщо декілька кунаїв досягають однієї точки одночасно, вони зіштовхуються і зникають. Розмір куная настільки малий, що його можна знехтувати. Також, оскільки ніндзя можуть швидко рухатися, вони не будуть зачеплені кунаєм. Кунай летить по прямій, не втрачаючи швидкості, поки не зіткнеться з іншим кунаєм.

На наступних рисунках стрілки позначають кунай. Напрямок стрілок вказує напрямок руху куная. На цих рисунках всі жирні стрілки зіткнуться.

На наступних рисунках жирні стрілки не будуть стикатися. На другому і третьому рисунку тонка стрілка зіткнеться з жирною. Оскільки зіткнуті стрілки зникнуть, товста стрілка не зіткнеться з іншою стрілкою на кожному з цих рисунків.

Завдання

Порахуйте кількість клітинок, через які пролетять кунаї, після того, як пройде достатньо часу.

Обмеження

$1 \leq n \leq 100000$ 1 \leq n \leq 100000 - кількість ніндзя

$1 \leq w \leq 1000000000$ 1 \leq w \leq 1000000000, $1 \leq h \leq 1000000000$ 1 \leq h \leq 1000000000 - розміри сітки

$1 \leq x_{i} \leq w$ 1 \leq x_i \leq w, $1 \leq y_{i} \leq h$ 1 \leq y_i \leq h - координати ніндзя

Вхідні дані

Перший рядок містить два цілих числа $w$ і $h$ , що описують розмір сітки. Другий рядок містить число $n$ - кількість ніндзя. Далі йдуть $n$ рядків. $i$ -й рядок ( $1 \leq i \leq n$ 1 \leq i \leq n) містить три цілі числа, розділені пробілом: $x_{i}$ x_i, $y_{i}$ y_i, $d_{i}$ d_i, які вказують на позицію $i$ -го ніндзя (стовпець $x_{i}$ x_i зліва і рядок $y_{i}$ y_i зверху) і його напрямок $d_{i}$ d_i. Жодні два ніндзя не знаходяться в одній позиції. Значення $d_{i}$ d_i описані нижче:

Якщо $d_{i} = 0$ d_i = 0, то $i$ -й ніндзя дивиться вправо.
Якщо $d_{i} = 1$ d_i = 1, то $i$ -й ніндзя дивиться вгору.
Якщо $d_{i} = 2$ d_i = 2, то $i$ -й ніндзя дивиться вліво.
Якщо $d_{i} = 3$ d_i = 3, то $i$ -й ніндзя дивиться вниз.

Вихідні дані

Виведіть кількість клітинок у сітці $w \times h$ w \times h, через які пролетять кунаї через достатню кількість часу.

Приклади

Приклад 1

Примітка

Приклад 1

У момент часу $0$ сітка виглядає наступним чином:

Кунай, кинутий $i$ -тим ніндзя, позначається як $i$ . У момент часу $0.5$ , кунай $2$ і кунай $3$ зіткнуться і зникнуть. Наступний рисунок описує момент часу $1$ . Сірі клітинки позначають клітинки, через які кунаї вже пролетіли.

У момент часу $2$ , кунай $1$ і кунай $5$ зіткнуться і зникнуть. Сітка у момент часу $2$ описана нижче.

Жодні кунаї після моменту часу $2$ більше не зіткнуться. Після достатньої кількості часу сітка виглядатиме наступним чином:

Загалом, кількість клітинок, пройдених кунаями, дорівнює $11$ . Тому ми повинні вивести число $11$ .