Кунай
Кунай — це зброя у формі ножа, яку використовують ніндзя. Ніндзя атакують ворога, кидаючи в нього кунай.
На сітці розміром w стовпців і h рядків розташовано n ніндзя. Кожен ніндзя знаходиться в центрі своєї клітинки, і жодні два ніндзя не займають одну й ту саму клітинку. У кожного ніндзя є кунай, і кожен дивиться в одному з чотирьох напрямків: вгору, вниз, вліво або вправо. У момент часу 0 кожен ніндзя кидає свій кунай у напрямку, в якому він дивиться.
Кожен кунай летить прямо зі швидкістю 1. Якщо декілька кунаїв досягають однієї точки одночасно, вони зіштовхуються і зникають. Розмір куная настільки малий, що його можна знехтувати. Також, оскільки ніндзя можуть швидко рухатися, вони не будуть зачеплені кунаєм. Кунай летить по прямій, не втрачаючи швидкості, поки не зіткнеться з іншим кунаєм.
На наступних рисунках стрілки позначають кунай. Напрямок стрілок вказує напрямок руху куная. На цих рисунках всі жирні стрілки зіткнуться.
На наступних рисунках жирні стрілки не будуть стикатися. На другому і третьому рисунку тонка стрілка зіткнеться з жирною. Оскільки зіткнуті стрілки зникнуть, товста стрілка не зіткнеться з іншою стрілкою на кожному з цих рисунків.
Завдання
Порахуйте кількість клітинок, через які пролетить кунай, після того, як пройде достатньо часу.
Обмеження
1 ≤ n ≤ 100000 - кількість ніндзя 1 ≤ w ≤ 1000000000, 1 ≤ h ≤ 1000000000 - розміри сітки 1 ≤ x_i ≤ w, 1 ≤ y_i ≤ h - координати ніндзя
Вхідні дані
Перший рядок містить два цілих числа w і h, що описують розмір сітки. Другий рядок містить число n - кількість ніндзя. Далі йдуть n рядків. i-й рядок (1 ≤ i ≤ n) містить три цілі числа, розділені пробілом: x_i, y_i, d_i, які вказують на позицію i-го ніндзя (стовпець x_i зліва і рядок y_i зверху) і його напрямок d_i. Жодні два ніндзя не знаходяться в одній позиції. Значення d_i описані нижче:
Якщо d_i = 0, то i-й ніндзя дивиться вправо.
Якщо d_i = 1, то i-й ніндзя дивиться вгору.
Якщо d_i = 2, то i-й ніндзя дивиться вліво.
Якщо d_i = 3, то i-й ніндзя дивиться вниз.
Вихідні дані
Виведіть кількість клітинок у сітці w×h, через які пролетить кунай через достатню кількість часу.
Примітка до прикладу 1
У момент часу 0 сітка виглядає наступним чином:
Кунай, кинутий i-тим ніндзя, позначається як i. У момент часу 0.5, кунай 2 і кунай 3 зіткнуться і зникнуть. Наступний рисунок описує момент часу 1. Сірі клітинки позначають клітинки, через які кунай вже пролетіли.
У момент часу 2, кунай 1 і кунай 5 зіткнуться і зникнуть. Сітка у момент часу 2 описана нижче.
Жодні кунай після моменту часу 2 більше не зіткнуться. Після достатньої кількості часу сітка виглядатиме наступним чином:
Загалом, кількість клітинок, пройдених кунай, дорівнює 11. Тому ми повинні вивести число 11.