Фермер Лёша владеет полем размера n клеток на m клеток. Позиция каждой клетки характеризуется парой чисел (i, j), которые обозначают номер строки и номер столбца соответственно. Каждая клетка этого поля является либо травой (обозначается символом '.') либо камнем (обозначается символом 'X').

Случилось несчастье — на поле начался пожар. Огонь начал разгораться из разных источников. Всего есть k источников огня. i-ый источник огня начал гореть из клетки с травой c координатами (x_i, y_i) и будет гореть c_i секунд. Каждую секунду огонь распространяется на соседние по сторонам клетки. Если в текущей клетке огню осталось горесть c секунд, то в соседней клетке, на которую он распространяется, ему останется гореть c - 1 секунду. Огонь из текущей клетки не распространяется, если ему остаётся гореть 0 секунд. Можно считать, что все огни горят независимо, то есть распространение огня никак не зависит от другого огня. Все источники огня имеют различные координаты. Камень не горит.

Лёше очень интересно, сколько же клеток с травой будут затронуты пожаром.