시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 417 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+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yjg1Y1x1YmQwN1x1Yzc3NCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0XHVjOWMwIFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1ZDJiOFx1Yjc5OSBcdWM3MDRcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWFjZTBcdWM4MTVcdWI0MWMgXHVjODcwXHVjMGFjXHVjODEwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU4OFx1YjJlNC4gXHViODVjXHViZDA3XHVjNzQwIFx1YmE4NVx1YjgzOVx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NjAgXHViNTRjXHViOWM4XHViMmU0LCBcdWFjMDEgXHVjODcwXHVjMGFjXHVjODEwXHVhY2ZjXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNWQwXHVhYzhjIFx1YzgwNFx1YzFhMVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViOWU4XHVkNTc0XHVkMmJjIFx1YWM3MFx1YjlhY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViODVjXHViZDA3XHVjNzc0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWM4MDRcdWMxYTFcdWQ1NWMgXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODcwXHVjMGFjXHVjODEwXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YmE4NVx1YjgzOVx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDAsIDEgJmxlOyBNICZsZTsgMzAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzg3MFx1YzBhY1x1YzgxMFx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHVjNzU4IFx1YzgwOFx1YjMwMFx1YWMxMlx1Yzc0MCBcdWJjMzFcdWI5Y2NcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YWMxOVx1Yzc0MCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVhYzAwXHVjOWMwXHViMjk0IFx1Yzg3MFx1YzBhY1x1YzgxMFx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGNcdWIyOTQsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHViNTMwXHViODVjIFx1YWNjNFx1YzBiMFx1ZDU3NFx1YzExYyBcdWQ1NjlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWI4NWNcdWJkMDdcdWM1ZDBcdWFjOGMgXHVjODA0XHVjMWExXHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc3NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgTVx1YzkwNFx1Yzc3NFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQsIGlcdWJjODhcdWM5ZjggXHViYTg1XHViODM5XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YWNlMCBcdWIwOWMgXHVkNmM0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWM4MDRcdWMxYTFcdWQ1NWMgXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUk9CT1QiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGNyZWF0ZWQgYSBuZXcgcm9ib3QgYW5kIGRlY2lkZWQgdG8gdGVzdCBpdCBvbiBhIGdpYW50IHRlc3QgdHJhY2suIFdlIGNhbiBpbWFnaW5lIHRoZSB0ZXN0IHRyYWNrIGFzIDJEIGNvb3JkaW5hdGUgc3lzdGVtLiBUaGUgcm9ib3Qgc3RhcnRzIGF0IGEgcG9pbnQgKDAsIDApIGFuZCByZWNlaXZlcyBhIHNldCBvZiBpbnN0cnVjdGlvbnMgZGVub3RlZCBieSBsZXR0ZXJzIFMsIEosIEksIFosIGVhY2ggb2YgdGhlbSBtYXJraW5nIGEgZGlyZWN0aW9uIGluIHdoaWNoIHJvYm90IHNob3VsZCBiZSBtb3ZpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1vcmUgcHJlY2lzZWx5LCBpZiBhIHJvYm90IGlzIGxvY2F0ZWQgaW4gKHgsIHkpLCBTICgmbGRxdW87bm9ydGgmcmRxdW87KSBtZWFucyBpdCBzaG91bGQgbW92ZSB0byAoeCwgeSsxKSwgSiAoJmxkcXVvO3NvdXRoJnJkcXVvOykgbWVhbnMgaXQgc2hvdWxkIG1vdmUgdG8gKHgsIHktMSksIEkgKCZsZHF1bztlYXN0JnJkcXVvOykgbWVhbnMgaXQgc2hvdWxkIG1vdmUgdG8gKHgrMSwgeSkgYW5kIFogKCZsZHF1bzt3ZXN0JnJkcXVvOykgbWVhbnMgaXQgc2hvdWxkIG1vdmUgdG8gKHgtMSwgeSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoaWxlIHJvYm90IGlzIHJlY2VpdmluZyBpbnN0cnVjdGlvbnMgYW5kIG1vdmVzIHRocm91Z2ggdGhlIHRlc3QgdHJhY2ssIE1pcmtvIGlzIHZlcmlmeWluZyBpdHMgcG9zaXRpb24gaW4gdGhlIGZvbGxvd2luZyBtYW5uZXIuIFRlc3QgdHJhY2sgY29udGFpbnMgTiBmaXhlZCBjb250cm9sIHBvaW50cy4gQWZ0ZXIgZWFjaCBpbnN0cnVjdGlvbiBpcyBtYWRlLCBlYWNoIG9mIHRoZSBjb250cm9sIHBvaW50cyBtZWFzdXJlcyBtYW5oYXR0YW4tZGlzdGFuY2UgdG8gdGhlIHJvYm90LiBEaXN0YW5jZXMgZnJvbSBhbGwgY29udHJvbCBwb2ludHMgYXJlIHRoZW4gc3VtbWVkIGFuZCBzZW50IHRvIE1pcmtvLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Bc3N1bWluZyB0aGF0IHJvYm90IG1vdmVzIGJ5IHRoZSBpbnN0cnVjdGlvbnMgd2l0aG91dCBlcnJvciwgY2FsY3VsYXRlIHRoZSBzdW0gb2YgZGlzdGFuY2VzIHRvIGFsbCBjb250cm9sIHBvaW50cyBhZnRlciBlYWNoIGluc3RydWN0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5SZW1hcms6IG1hbmhhdHRhbi1kaXN0YW5jZSBvZiB0aGUgcG9pbnRzICh4MSwgeTEpIGFuZCAoeDIsIHkyKSBpcyBlcXVhbCB0byB8eDEgLSB4MnwgKyB8eTEgLSB5MnwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHBvc2l0aXZlIGludGVnZXJzIE4gKG51bWJlciBvZiBjb250cm9sIHBvaW50cywgMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSBhbmQgTSAobnVtYmVyIG9mIGluc3RydWN0aW9ucywgMSAmbGU7IE0gJmxlOyAzMDAgMDAwKSwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBjb29yZGluYXRlcyBvZiBvbmUgY29udHJvbCBwb2ludDogdHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB4LCB5LCB3aXRoIGFic29sdXRlIHZhbHVlIGxlc3MgdGhhbiAxIDAwMCAwMDAgKG1pbGxpb24pLiBJdCBpcyBwb3NzaWJsZSB0aGF0IHR3byBjb250cm9sIHBvaW50cyBoYXZlIHRoZSBzYW1lIGNvb3JkaW5hdGVzIC0gZGlzdGFuY2UgdG93YXJkcyBlYWNoIG9mIHRoZW0gaXMgYWRkZWQgdG8gdGhlIHN1bS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nIG9mIE0gY2hhcmFjdGVycyBmcm9tIHRoZSBzZXQge1MsIEosIEksIFp9LCB0aGUgc2VxdWVuY2Ugb2YgaW5zdHJ1Y3Rpb25zIHNlbnQgdG8gdGhlIHJvYm90LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBNIGxpbmVzOiBpLXRoIGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBkZXNjcmliZWQgbnVtYmVyIGFmdGVyIGktdGggaW5zdHJ1Y3Rpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==