Олимпиадный тренинг

Задача . Параллельное программирование


Миша занимается параллельным программированием. Сегодня он пишет программу для исполнителя "Квадратик". Исполнитель "Квадратик" живет на клетчатом поле размера  N х M, размер одной клетки 1х1. Перемещаясь он закрашивает клетку, на которой побывал. Клетку, на которой он начал движение и на которой остановился он также закрашивает. 
Миша установил на поле K "Квадратиков". Каждый "Квадратик" будет двигаться в указанном Мишей направлении и останавливаться дойдя до конца поля. После окончании движения всех "Квадратиков", Миша хочет узнать сколько клеток поля получились закрашенными. Так как задача подсчета не относится к параллельному программированию, а размер поля может быть очень большим, Миша попросил вас написать программу для подсчета таких клеток.
 

Входные данные

Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры поля исполнителя "Квадратик" (1 <= M, N <= 106). Во второй строке записано число K - количество "Квадратиков" на поле (0 <= K <= 103). Далее идут K строк, каждая из которых описывает положение определенного "Квадратика" и направление, в котором он будет перемещаться. Формат каждой из таких строк: два целых числа, записанных через один пробел и один символ  {NESW} - начальные координаты и направление движения соответствующего "Квадратика". Символ отделен от чисел ровно одним пробелом. 
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.


Выходные данные

Выведите количество закрашенных клеток поля, после окончания движения всех "Квадратиков".


Пояснения
Поле исполнителя и расположение "Квадратиков" для первого примера, показаны на рисунке ниже. Стрелочкой обозначено направление движения соответствующего "Квадратика".

 
Примеры
Входные данные Выходные данные
1
8 5
4
4 4 S
6 2 W
6 3 N
6 4 S
13

time 3000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python4
Комментарий учителя