Муравьи на кубической Земле
В условиях данной задачи будем пользоваться предположением, что Земля имеет форму куба, и каждая грань - квадрат m×m, расчерченный на клетки размером 1×1.
В начальный момент времени n муравьев стоят на верхней грани этого куба. Каждый муравей направлен в одну из четырех сторон - на север, на юг, на запад или на восток.
В определенный момент муравьи начинают двигаться по прямой, каждый в своем направлении. Когда муравей доползает до ребра куба, он переползает через него и продолжает движение по следующей грани. При этом он все время движется перпендикулярно тому ребру, которое переполз.
Такое движение продолжается бесконечно долго. Выясните, сколько есть клеток на кубе, на которых ни разу во время этого процесса не побывает ни один муравей.
Входные данные
В первой строчке входного файла содержатся два натуральных числа - n и m - количество муравьев на Земле и длина стороны планеты (1 ≤ n ≤ 100000; 1 ≤ m ≤ 15000).
В каждой из следующий n строчек находится описание начального положения очередного муравья. Сначала идут два натуральных числа x и y - координаты муравья на верхней грани, а затем символ, задающий направление муравья - 'N', 'S', 'W' или 'E'. Числа и символ разделяются ровно одним пробелом.
Оси координат и направления сторон света приведены на рисунке. Все координаты лежат в интервале от 1 до m включительно.
Несколько муравьев как в начальный момент времени, так и в любой другой, могут оказаться на одной клетке. Это никак не влияет на траектории их движения.
Выходные данные
В выходной файл выведите одно число - количество клеток, никогда не посещаемых муравьями.
