Кунай
Кунай - оружие в форме ножа, используемое ниндзя. Ниндзя атакуют врага, бросая в них кунай.
На сетке из 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.