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