Робот
Ібрагім створив нового робота і вирішив протестувати його на гігантському тестовому треку. Ми можемо уявити тестовий трек як 2D координатну систему. Робот починає в точці (0,0) і отримує набір інструкцій, позначених літерами S, J, I, Z, кожна з яких вказує напрямок, в якому робот повинен рухатися. Точніше, якщо робот знаходиться в (x,y), S (“північ”) означає, що він повинен рухатися до (x,y+1), J (“південь”) означає, що він повинен рухатися до (x,y-1), I (“схід”) означає, що він повинен рухатися до (x+1,y), а Z (“захід”) означає, що він повинен рухатися до (x-1,y).
Поки робот отримує інструкції і рухається по тестовому треку, Ібрагім перевіряє його позицію наступним чином. Тестовий трек містить N фіксованих контрольних точок. Після кожної інструкції кожна з контрольних точок вимірює мангеттенську відстань до робота. Відстані від усіх контрольних точок підсумовуються і відправляються Ібрагіму. Припускаючи, що робот рухається за інструкціями без помилок, обчисліть суму відстаней до всіх контрольних точок після кожної інструкції.
Примітка: мангеттенська відстань між точками (x1,y1) і (x2, y2) дорівнює |x1 - x2| + |y1 – y2|.
Вхідні дані
Перша строка вхідних даних містить додатні цілі числа N (кількість контрольних точок, 1 ≤ N ≤ 100 000) та M (кількість інструкцій, 1 ≤ M ≤ 300 000), розділені одним пробілом.Кожна з наступних N строк містить координати однієї контрольної точки: два цілі числа, розділені пробілом x, y, з абсолютним значенням менше 1 000 000 (мільйон). Можливо, що дві контрольні точки мають однакові координати - відстань до кожної з них додається до суми.Наступна строка містить рядок з M символів з множини {S, J, I, Z}, послідовність інструкцій, надісланих роботу.
Вихідні дані
Виведіть M рядків: i-й рядок виходу повинен містити описане число після i-ї інструкції.