Задачі
Мурашки на кубічній Землі
Мурашки на кубічній Землі
В умовах даної задачі будемо користуватись припущенням, що Земля має форму куба, і кожна грань - квадрат \textbf{m}×\textbf{m}, розділений на клітинки розміром \textbf{1}×\textbf{1}.
У початковий момент часу \textbf{n} мурашок стоять на верхній грані цього кубу. Кожна мурашка направлена в одну з чотирьох сторін - на північ, на південь, на захід чи на схід.
У певний момент мурашки починають рухатись по прямій, кожнай у своєму напрямку. Коли мурашка доповзає до ребра куба, вона переповзає через нього і продовжує рух по наступній грані. При цьому вона весь час рухається перпендикулярно до того ребра, яке переповзла.
Такий рух продовжується нескінченно довго. Виясніть, скільки є клітинок на кубі, на яких жодного разу під час цього процесу не побуває жодна мурашка.
\InputFile
У першому рядочку вихідного файлу міститься два натуральних числа - \textbf{n} та \textbf{m} - кількість мурашок на Землі та довжина сторони планети (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}; \textbf{1} ≤ \textbf{m} ≤ \textbf{15000}).
У кожному з наступних \textbf{n} рядків знаходиться опис початкового положення чергової мурашки. Спочатку йдуть два натуральних числа \textbf{x} та \textbf{y} - координати мурашки на верхній грані, а потім символ, який задає напрям мурашки - '\textbf{N}', '\textbf{S}', '\textbf{W}' чи '\textbf{E}'. Числа та символ відокремлюються рівно одним пропуском.
Осі координат та напрямки сторін світу наведено на рисунку. Усі координати лежать в інтервалі від \textbf{1 }до \textbf{m} включно.
Декілька мурашок як у початковий момент часу, так і у довільний інший, можуть опинись на одній клітиці. Це ніяк не пвливає на траекторію їх руху.
\OutputFile
У вихідний файл виведіть одне число - кількість клітинок, які ніколи не відвідуються мурашками.
\includegraphics{https://static.e-olymp.com/content/a9/a9cda1ad995458d253c1a989915664db22c4d690.jpg}
Вхідні дані #1
2 4 2 2 N 4 3 W
Вихідні дані #1
66