시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB82825618737.103%

문제

상근이는 새로운 로봇을 만들었다. 이 로봇의 성능을 시험하기 위해서 테스트 트랙 위에서 테스트하기로 했다. 테스트 트랙은 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

1 3
0 -10
ISI

예제 출력 1

11
12
13

예제 입력 2

3 5
0 0
1 1
1 -1
SIJJZ

예제 출력 2

5
4
3
4
5
W3sicHJvYmxlbV9pZCI6IjI4MTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMwYzFcdWFkZmNcdWM3NzRcdWM3NTggXHViODVjXHViZDA3IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1Yjg1Y1x1YmQwN1x1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1Yzc3NCBcdWI4NWNcdWJkMDdcdWM3NTggXHVjMTMxXHViMmE1XHVjNzQ0IFx1YzJkY1x1ZDVkOFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OSBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4XHVkNTU4XHVhZTMwXHViODVjIFx1ZDU4OFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OVx1Yzc0MCAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1Yzc3NFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWI4NWNcdWJkMDdcdWM3NDAgKDAsMClcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViODVjXHViZDA3XHVjNWQwXHVhYzhjIFMsIEosIEksIFpcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWJjZjRcdWIwYjhcdWIyZTQuIFx1Yzc3NCBcdWJhODVcdWI4MzlcdWM3NDAgXHViODVjXHViZDA3XHVjNzc0IFx1YzZjMFx1YzljMVx1YzVlY1x1YzU3YyBcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODVjXHViZDA3XHVjNzc0IFx1ZDYwNFx1YzdhYyAoeCx5KVx1YzVkMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBTKG5vcnRoKVx1YjI5NCAoeCwgeSsxKVx1Yjg1YywgSihzb3V0aClcdWIyOTQgKHgseS0xKVx1Yjg1YywgSShlYXN0KVx1YjI5NCAoeCsxLHkpXHViODVjLCBaKHdlc3QpXHViMjk0ICh4LTEseSlcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0XHVjOWMwIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OSBcdWM3MDRcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWFjZTBcdWM4MTVcdWI0MWMgXHVjODcwXHVjMGFjXHVjODEwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU4OFx1YjJlNC4gXHViODVjXHViZDA3XHVjNzQwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWFjMDEgXHVjODcwXHVjMGFjXHVjODEwXHVhY2ZjXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzgwNFx1YzFhMVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViOWU4XHVkNTc0XHVkMmJjIFx1YWM3MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODVjXHViZDA3XHVjNzc0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWM4MDRcdWMxYTFcdWQ1NWMgXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4NzBcdWMwYWNcdWM4MTBcdWM3NTggXHVjMjE4IE5cdWFjZmMgXHViYTg1XHViODM5XHVjNzU4IFx1YzIxOCBNXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgMSAmbGU7IE0gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODcwXHVjMGFjXHVjODEwXHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWM2NDAgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWM3NTggXHVjODA4XHViMzEzXHVhYzEyXHVjNzQwIFx1YmMzMVx1YjljY1x1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjODcwXHVjMGFjXHVjODEwXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0Y1x1YjI5NCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWI1MzBcdWI4NWMgXHVhY2M0XHVjMGIwXHVkNTc0XHVjMTFjIFx1ZDU2OVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yjg1Y1x1YmQwN1x1YzVkMFx1YWM4YyBcdWM4MDRcdWMxYTFcdWQ1NWMgXHViYTg1XHViODM5XHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1Y2QxZCBNXHVjOTA0XHVjNzc0XHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCwgaVx1YmM4OFx1YzlmOCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHVhY2UwIFx1YjA5YyBcdWQ2YzRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzgwNFx1YzFhMVx1ZDU1YyBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI4MTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJST0JPVCIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gY3JlYXRlZCBhIG5ldyByb2JvdCBhbmQgZGVjaWRlZCB0byB0ZXN0IGl0IG9uIGEgZ2lhbnQgdGVzdCB0cmFjay4gV2UgY2FuIGltYWdpbmUgdGhlIHRlc3QgdHJhY2sgYXMgMkQgY29vcmRpbmF0ZSBzeXN0ZW0uIFRoZSByb2JvdCBzdGFydHMgYXQgYSBwb2ludCAoMCwgMCkgYW5kIHJlY2VpdmVzIGEgc2V0IG9mIGluc3RydWN0aW9ucyBkZW5vdGVkIGJ5IGxldHRlcnMgUywgSiwgSSwgWiwgZWFjaCBvZiB0aGVtIG1hcmtpbmcgYSBkaXJlY3Rpb24gaW4gd2hpY2ggcm9ib3Qgc2hvdWxkIGJlIG1vdmluZy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TW9yZSBwcmVjaXNlbHksIGlmIGEgcm9ib3QgaXMgbG9jYXRlZCBpbiAoeCwgeSksIFMgKCZsZHF1bztub3J0aCZyZHF1bzspIG1lYW5zIGl0IHNob3VsZCBtb3ZlIHRvICh4LCB5KzEpLCBKICgmbGRxdW87c291dGgmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeCwgeS0xKSwgSSAoJmxkcXVvO2Vhc3QmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeCsxLCB5KSBhbmQgWiAoJmxkcXVvO3dlc3QmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeC0xLCB5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hpbGUgcm9ib3QgaXMgcmVjZWl2aW5nIGluc3RydWN0aW9ucyBhbmQgbW92ZXMgdGhyb3VnaCB0aGUgdGVzdCB0cmFjaywgTWlya28gaXMgdmVyaWZ5aW5nIGl0cyBwb3NpdGlvbiBpbiB0aGUgZm9sbG93aW5nIG1hbm5lci4gVGVzdCB0cmFjayBjb250YWlucyBOIGZpeGVkIGNvbnRyb2wgcG9pbnRzLiBBZnRlciBlYWNoIGluc3RydWN0aW9uIGlzIG1hZGUsIGVhY2ggb2YgdGhlIGNvbnRyb2wgcG9pbnRzIG1lYXN1cmVzIG1hbmhhdHRhbi1kaXN0YW5jZSB0byB0aGUgcm9ib3QuIERpc3RhbmNlcyBmcm9tIGFsbCBjb250cm9sIHBvaW50cyBhcmUgdGhlbiBzdW1tZWQgYW5kIHNlbnQgdG8gTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFzc3VtaW5nIHRoYXQgcm9ib3QgbW92ZXMgYnkgdGhlIGluc3RydWN0aW9ucyB3aXRob3V0IGVycm9yLCBjYWxjdWxhdGUgdGhlIHN1bSBvZiBkaXN0YW5jZXMgdG8gYWxsIGNvbnRyb2wgcG9pbnRzIGFmdGVyIGVhY2ggaW5zdHJ1Y3Rpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlJlbWFyazogbWFuaGF0dGFuLWRpc3RhbmNlIG9mIHRoZSBwb2ludHMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGlzIGVxdWFsIHRvIHx4MSAtIHgyfCArIHx5MSAtIHkyfC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgcG9zaXRpdmUgaW50ZWdlcnMgTiAobnVtYmVyIG9mIGNvbnRyb2wgcG9pbnRzLCAxICZsZTsgTiAmbGU7IDEwMCAwMDApIGFuZCBNIChudW1iZXIgb2YgaW5zdHJ1Y3Rpb25zLCAxICZsZTsgTSAmbGU7IDMwMCAwMDApLCBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGNvb3JkaW5hdGVzIG9mIG9uZSBjb250cm9sIHBvaW50OiB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIHgsIHksIHdpdGggYWJzb2x1dGUgdmFsdWUgbGVzcyB0aGFuIDEgMDAwIDAwMCAobWlsbGlvbikuIEl0IGlzIHBvc3NpYmxlIHRoYXQgdHdvIGNvbnRyb2wgcG9pbnRzIGhhdmUgdGhlIHNhbWUgY29vcmRpbmF0ZXMgLSBkaXN0YW5jZSB0b3dhcmRzIGVhY2ggb2YgdGhlbSBpcyBhZGRlZCB0byB0aGUgc3VtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGxpbmUgY29udGFpbnMgYSBzdHJpbmcgb2YgTSBjaGFyYWN0ZXJzIGZyb20gdGhlIHNldCB7UywgSiwgSSwgWn0sIHRoZSBzZXF1ZW5jZSBvZiBpbnN0cnVjdGlvbnMgc2VudCB0byB0aGUgcm9ib3QuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE0gbGluZXM6IGktdGggbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGRlc2NyaWJlZCBudW1iZXIgYWZ0ZXIgaS10aCBpbnN0cnVjdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #3 4번