Робот
Ибрагим создал нового робота и решил испытать его на огромной тестовой трассе. Мы можем представить эту трассу как двумерную координатную систему. Робот стартует из точки (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-й команды.