Миша занимается параллельным программированием. Сегодня он пишет программу для исполнителя "Квадратик". Исполнитель "Квадратик" живет на клетчатом поле размера N х M, размер одной клетки 1х1. Перемещаясь он закрашивает клетку, на которой побывал. Клетку, на которой он начал движение и на которой остановился он также закрашивает.
Миша установил на поле K "Квадратиков". Каждый "Квадратик" будет двигаться в указанном Мишей направлении и останавливаться дойдя до конца поля. После окончании движения всех "Квадратиков", Миша хочет узнать сколько клеток поля получились закрашенными. Так как задача подсчета не относится к параллельному программированию, а размер поля может быть очень большим, Миша попросил вас написать программу для подсчета таких клеток.
Входные данные
Программа получает на вход несколько строк. Первая строка содержит целые числа M и N - размеры поля исполнителя "Квадратик" (1 <= M, N <= 106). Во второй строке записано число K - количество "Квадратиков" на поле (0 <= K <= 103). Далее идут K строк, каждая из которых описывает положение определенного "Квадратика" и направление, в котором он будет перемещаться. Формат каждой из таких строк: два целых числа, записанных через один пробел и один символ {N, E, S, W} - начальные координаты и направление движения соответствующего "Квадратика". Символ отделен от чисел ровно одним пробелом.
Символами обозначены следующие направления движения: N - вверх, S - вниз, W - влево, Е - вправо.
Выходные данные
Выведите количество закрашенных клеток поля, после окончания движения всех "Квадратиков".
Пояснения
Поле исполнителя и расположение "Квадратиков" для первого примера, показаны на рисунке ниже. Стрелочкой обозначено направление движения соответствующего "Квадратика".
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
8 5
4
4 4 S
6 2 W
6 3 N
6 4 S
|
13
|