Робот#9431

Робот

1 секунда

32 мегабайти

Середня

Ібрагім створив нового робота і вирішив протестувати його на гігантському тестовому треку. Ми можемо уявити тестовий трек як 2D координатну систему. Робот починає в точці $(0, 0)$ і отримує набір інструкцій, позначених літерами S, J, I, Z, кожна з яких вказує напрямок, в якому робот повинен рухатися. Точніше, якщо робот знаходиться в $(x, y)$ , S ("північ") означає, що він повинен рухатися до $(x, y + 1)$ (x,y+1), J ("південь") означає, що він повинен рухатися до $(x, y - 1)$ (x,y-1), I ("схід") означає, що він повинен рухатися до $(x + 1, y)$ (x+1,y), а Z ("захід") означає, що він повинен рухатися до $(x - 1, y)$ (x-1,y).

Поки робот отримує інструкції і рухається по тестовому треку, Ібрагім перевіряє його позицію наступним чином. Тестовий трек містить $N$ фіксованих контрольних точок. Після кожної інструкції кожна з контрольних точок вимірює манхеттенську відстань до робота. Відстані від усіх контрольних точок підсумовуються і відправляються Ібрагіму. Припускаючи, що робот рухається за інструкціями без помилок, обчисліть суму відстаней до всіх контрольних точок після кожної інструкції.

Примітка: манхеттенська відстань між точками $(x_{1}, y_{1})$ (x_1, y_1) і $(x_{2}, y_{2})$ (x_2, y_2) дорівнює $∣ x_{1} - x_{2} ∣ + ∣ y_{1} - y_{2} ∣$ |x_1 - x_2| + |y_1 - y_2|.

Вхідні дані

Перший рядок вхідних даних містить додатні цілі числа $N$ (кількість контрольних точок, $1 \leq N \leq 100000$ 1 \le N \le 100\,000) та $M$ (кількість інструкцій, $1 \leq M \leq 300000$ 1 \le M \le 300\,000), розділені одним пробілом.

Кожен з наступних $N$ рядків містить координати однієї контрольної точки: два цілі числа, розділені пробілом $x$ , $y$ , з абсолютним значенням менше $1000000$ (мільйон). Можливо, що дві контрольні точки мають однакові координати — відстань до кожної з них додається до суми.

Наступний рядок містить рядок з $M$ символів з множини {S, J, I, Z}, послідовність інструкцій, надісланих роботу.

Вихідні дані

Виведіть $M$ рядків: $i$ -й рядок виводу повинен містити описане число після $i$ -ї інструкції.

Приклади

Приклад 1

Приклад 2