Мурашки на кубічній Землі#4884
У цій задачі припускається, що Земля має форму куба, де кожна грань — це квадрат розміром m \times m, розділений на клітини 1 \times 1.
Спочатку мурах розташовані на верхній грані цього куба. Кожна мураха спрямована в один з чотирьох напрямків: на північ, на південь, на захід або на схід.
У певний момент мурахи починають рухатися по прямих, кожна — у своєму початковому напрямку. Коли мураха доходить до межі куба, вона переходить на наступну грань і продовжує рух перпендикулярно до межі, яку перетнула.
Цей рух триває безкінечно. Ваше завдання — визначити, скільки клітин на кубі ніколи не буде відвідано жодною мурахою в процесі цього руху.
У першому рядку вхідних даних розміщено два натуральних числа та — кількість мурах на Землі та довжину сторони куба (1 \leq n \leq 100\,000; 1 \leq m \leq 15\,000).
Кожен з наступних рядків описує початкове розташування мурахи. У кожному рядку вказано два натуральних числа і — координати мурахи на верхній грані, а також символ, що позначає напрямок руху: 'N', 'S', 'W' або 'E'. Числа та символ розділені рівно одним пробілом.
Напрямки координатних осей та сторін куба зображені на малюнку. Усі координати знаходяться в межах від до включно.
Кілька мурах можуть знаходитися в одній і тій самій клітині як у початковий момент, так і в будь-який інший момент часу, це жодним чином не впливає на їх шлях.
Виведіть єдине число — кількість клітин, які жодна мураха ніколи не відвідає.
Приклад 1