시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 415 123 89 37.712%

문제

상근이는 새로운 로봇을 만들었다. 이 로봇의 성능을 시험하기 위해서 테스트 트랙 위에서 테스트하기로 했다. 테스트 트랙은 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번째 명령을 수행하고 난 후에 상근이에게 전송한 값을 출력한다.

예제 입력 1

3 5
0 0
1 1
1 -1
SIJJZ

예제 출력 1

5
4
3
4
5
W3sicHJvYmxlbV9pZCI6IjI4MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViODVjXHViZDA3IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWI4NWNcdWJkMDdcdWM3NTggXHVjMTMxXHViMmE1XHVjNzQ0IFx1YzJkY1x1ZDVkOFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OSBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OVx1Yzc0MCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1Yzc3NFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWI4NWNcdWJkMDdcdWM3NDAgKDAsMClcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViODVjXHViZDA3XHVjNWQwXHVhYzhjIFMsIEosIEksIFpcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1Yzc3NCBcdWJhODVcdWI4MzlcdWM3NDAgXHViODVjXHViZDA3XHVjNzc0IFx1YzZjMFx1YzljMVx1YzVlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViODVjXHViZDA3XHVjNzc0IFx1ZDYwNFx1YzdhYyAoeCx5KVx1YzVkMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBTKG5vcnRoKVx1YjI5NCAoeCwgeSsxKVx1Yjg1YywgSihzb3V0aClcdWIyOTQgKHgseS0xKVx1Yjg1YywgSShlYXN0KVx1YjI5NCAoeCsxLHkpXHViODVjLCBaKHdlc3QpXHViMjk0ICh4LTEseSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0XHVjOWMwIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OSBcdWM3MDRcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWFjZTBcdWM4MTVcdWI0MWMgXHVjODcwXHVjMGFjXHVjODEwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU4OFx1YjJlNC4gXHViODVjXHViZDA3XHVjNzQwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWFjMDEgXHVjODcwXHVjMGFjXHVjODEwXHVhY2ZjXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzgwNFx1YzFhMVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVhYzcwXHViOWFjXHViMjk0IFx1YjllOFx1ZDU3NFx1ZDJiYyBcdWFjNzBcdWI5YWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjODA0XHVjMWExXHVkNTVjIFx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzg3MFx1YzBhY1x1YzgxMFx1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWJhODVcdWI4MzlcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCAxICZsZTsgTSAmbGU7IDMwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4NzBcdWMwYWNcdWM4MTBcdWM3NTggeFx1Yzg4Y1x1ZDQ1Y1x1YzY0MCB5XHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWM4MDhcdWIzMDBcdWFjMTJcdWM3NDAgXHViYzMxXHViOWNjXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWM4NzBcdWMwYWNcdWM4MTBcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjU0Y1x1YjI5NCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWI1MzBcdWI4NWMgXHVhY2M0XHVjMGIwXHVkNTc0XHVjMTFjIFx1ZDU2OVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yjg1Y1x1YmQwN1x1YzVkMFx1YWM4YyBcdWM4MDRcdWMxYTFcdWQ1NWMgXHViYTg1XHViODM5XHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjZDljXHViODI1XHVjNzQwIFx1Y2QxZCBNXHVjOTA0XHVjNzc0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCwgaVx1YmM4OFx1YzlmOCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHVhY2UwIFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzgwNFx1YzFhMVx1ZDU1YyBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJST0JPVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gY3JlYXRlZCBhIG5ldyByb2JvdCBhbmQgZGVjaWRlZCB0byB0ZXN0IGl0IG9uIGEgZ2lhbnQgdGVzdCB0cmFjay4gV2UgY2FuIGltYWdpbmUgdGhlIHRlc3QgdHJhY2sgYXMgMkQgY29vcmRpbmF0ZSBzeXN0ZW0uIFRoZSByb2JvdCBzdGFydHMgYXQgYSBwb2ludCAoMCwgMCkgYW5kIHJlY2VpdmVzIGEgc2V0IG9mIGluc3RydWN0aW9ucyBkZW5vdGVkIGJ5IGxldHRlcnMgUywgSiwgSSwgWiwgZWFjaCBvZiB0aGVtIG1hcmtpbmcgYSBkaXJlY3Rpb24gaW4gd2hpY2ggcm9ib3Qgc2hvdWxkIGJlIG1vdmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9yZSBwcmVjaXNlbHksIGlmIGEgcm9ib3QgaXMgbG9jYXRlZCBpbiAoeCwgeSksIFMgKCZsZHF1bztub3J0aCZyZHF1bzspIG1lYW5zIGl0IHNob3VsZCBtb3ZlIHRvICh4LCB5KzEpLCBKICgmbGRxdW87c291dGgmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeCwgeS0xKSwgSSAoJmxkcXVvO2Vhc3QmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeCsxLCB5KSBhbmQgWiAoJmxkcXVvO3dlc3QmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeC0xLCB5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hpbGUgcm9ib3QgaXMgcmVjZWl2aW5nIGluc3RydWN0aW9ucyBhbmQgbW92ZXMgdGhyb3VnaCB0aGUgdGVzdCB0cmFjaywgTWlya28gaXMgdmVyaWZ5aW5nIGl0cyBwb3NpdGlvbiBpbiB0aGUgZm9sbG93aW5nIG1hbm5lci4gVGVzdCB0cmFjayBjb250YWlucyBOIGZpeGVkIGNvbnRyb2wgcG9pbnRzLiBBZnRlciBlYWNoIGluc3RydWN0aW9uIGlzIG1hZGUsIGVhY2ggb2YgdGhlIGNvbnRyb2wgcG9pbnRzIG1lYXN1cmVzIG1hbmhhdHRhbi1kaXN0YW5jZSB0byB0aGUgcm9ib3QuIERpc3RhbmNlcyBmcm9tIGFsbCBjb250cm9sIHBvaW50cyBhcmUgdGhlbiBzdW1tZWQgYW5kIHNlbnQgdG8gTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzc3VtaW5nIHRoYXQgcm9ib3QgbW92ZXMgYnkgdGhlIGluc3RydWN0aW9ucyB3aXRob3V0IGVycm9yLCBjYWxjdWxhdGUgdGhlIHN1bSBvZiBkaXN0YW5jZXMgdG8gYWxsIGNvbnRyb2wgcG9pbnRzIGFmdGVyIGVhY2ggaW5zdHJ1Y3Rpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlJlbWFyazogbWFuaGF0dGFuLWRpc3RhbmNlIG9mIHRoZSBwb2ludHMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGlzIGVxdWFsIHRvIHx4MSAtIHgyfCArIHx5MSAtIHkyfC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgcG9zaXRpdmUgaW50ZWdlcnMgTiAobnVtYmVyIG9mIGNvbnRyb2wgcG9pbnRzLCAxICZsZTsgTiAmbGU7IDEwMCAwMDApIGFuZCBNIChudW1iZXIgb2YgaW5zdHJ1Y3Rpb25zLCAxICZsZTsgTSAmbGU7IDMwMCAwMDApLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGNvb3JkaW5hdGVzIG9mIG9uZSBjb250cm9sIHBvaW50OiB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHgsIHksIHdpdGggYWJzb2x1dGUgdmFsdWUgbGVzcyB0aGFuIDEgMDAwIDAwMCAobWlsbGlvbikuIEl0IGlzIHBvc3NpYmxlIHRoYXQgdHdvIGNvbnRyb2wgcG9pbnRzIGhhdmUgdGhlIHNhbWUgY29vcmRpbmF0ZXMgLSBkaXN0YW5jZSB0b3dhcmRzIGVhY2ggb2YgdGhlbSBpcyBhZGRlZCB0byB0aGUgc3VtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgTSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNldCB7UywgSiwgSSwgWn0sIHRoZSBzZXF1ZW5jZSBvZiBpbnN0cnVjdGlvbnMgc2VudCB0byB0aGUgcm9ib3QuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE0gbGluZXM6IGktdGggbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGRlc2NyaWJlZCBudW1iZXIgYWZ0ZXIgaS10aCBpbnN0cnVjdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d