시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 268 88 58 39.726%

문제

상근이는 새로운 로봇을 만들었다. 이 로봇의 성능을 시험하기 위해서 테스트 트랙 위에서 테스트하기로 했다. 테스트 트랙은 2차원 평면이다. 가장 처음에 로봇은 (0,0)에서 시작한다. 상근이는 로봇에게 S, J, I, Z중 하나의 명령을 보낸다. 이 명령은 로봇이 움직여야 하는 방향을 나타낸다.

로봇이 현재 (x,y)에 있다고 하자. S(north)는 (x, y+1)로, J(south)는 (x,y-1)로, I(east)는 (x+1,y)로, Z(west)는 (x-1,y)로 이동하라는 의미이다.

상근이는 로봇이 올바르게 움직이는지 확인하기 위해서 테스트 트랙 위에 N개의 고정된 조사점을 설치했다. 로봇은 명령을 수행할 때마다, 각 조사점과의 거리의 합을 상근이에게 전송한다. 이 때, 거리는 맨해튼 거리이다.

로봇이 상근이에게 전송한 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 조사점의 수 N과 명령의 수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000)

다음 N개 줄에는 조사점의 x좌표와 y좌표가 주어진다. 모든 좌표의 절대값은 백만보다 작거나 같은 정수이다. 같은 좌표를 가지는 조사점이 여러 개 있을 수도 있다. 이 때는, 각각의 거리를 따로 계산해서 합해야 한다.

마지막 줄에는 상근이가 로봇에게 전송한 명령이 순서대로 주어진다.

출력

출력은 총 M줄이다. i번째 줄에는, i번째 명령을 수행하고 난 후에 상근이에게 전송한 값을 출력한다.

예제 입력

3 5
0 0
1 1
1 -1
SIJJZ

예제 출력

5
4
3
4
5

힌트