시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 346 138 112 43.077%

문제

n*m 크기의 체스 판과, 상대팀의 Queen, Knight, Pawn의 위치가 주어져 있을 때, 안전한 칸이 몇 칸인지 세는 프로그램을 작성하시오. (안전한 칸이란 말은 그 곳에 자신의 말이 있어도 잡힐 가능성이 없다는 것이다.)

참고로 Queen은 가로, 세로, 대각선으로 갈 수 있는 만큼 최대한 많이 이동을 할 수 있는데 만약 그 중간에 장애물이 있다면 이동을 할 수 없다. 그리고 Knight는 2*3 직사각형을 그렸을 때, 반대쪽 꼭짓점으로 이동을 할 수 있다. 아래 그림과 같은 8칸이 이에 해당한다.

이때 Knight는 중간에 장애물이 있더라도 이동을 할 수 있다. 그리고 Pawn은 상대팀의 말은 잡을 수 없다고 하자(즉, 장애물의 역할만 한다는 것이다).

예를 들어 다음과 같이 말이 배치가 되어 있다면 진하게 표시된 부분이 안전한 칸이 될 것이다. (K : Knight, Q : Queen, P : Pawn)

입력

첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1<=n, m<=1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는
Knight의 개수와 위치, 넷째 줄에는 Pawn의 개수와 위치가 입력된다. (즉 둘째 줄~ 넷째 줄은  k,r1,c1,r2,c2,...,rk,ck 이 빈칸을 사이에 두고 주어진다는 것이다. 여기서 ri는 i번째 말의 행 위치, ci는 i번째 말의 열 위치를 의미한다.) 한 칸에는 하나의 말만 놓인다고 가정한다. Knight, Queen, Pawn의 개수는 각각 100을 넘지 않는다.

출력

첫째 줄에 n*m 체스판에 안전한 칸이 몇 칸인지 출력하시오.

예제 입력 1

4 4
2 1 4 2 4
1 1 2
1 2 3

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjE5ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPm4qbSBcdWQwNmNcdWFlMzBcdWM3NTggXHVjY2I0XHVjMmE0IFx1ZDMxMFx1YWNmYywgXHVjMGMxXHViMzAwXHVkMzAwXHVjNzU4IFF1ZWVuLCBLbmlnaHQsIFBhd25cdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWM1NDhcdWM4MDRcdWQ1NWMgXHVjZTc4XHVjNzc0IFx1YmE4NyBcdWNlNzhcdWM3NzhcdWM5YzAgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWM1NDhcdWM4MDRcdWQ1NWMgXHVjZTc4XHVjNzc0XHViNzgwIFx1YjlkMFx1Yzc0MCBcdWFkZjggXHVhY2YzXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWI5ZDBcdWM3NzQgXHVjNzg4XHVjNWI0XHViM2M0IFx1YzdhMVx1ZDc5MCBcdWFjMDBcdWIyYTVcdWMxMzFcdWM3NzQgXHVjNWM2XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1Y2MzOFx1YWNlMFx1Yjg1YyBRdWVlblx1Yzc0MCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YywgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWI5Y2NcdWM1N2QgXHVhZGY4IFx1YzkxMVx1YWMwNFx1YzVkMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0IFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIEtuaWdodFx1YjI5NCAyKjMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWRmOFx1YjgzOFx1Yzc0NCBcdWI1NGMsIFx1YmMxOFx1YjMwMFx1Y2FiZCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc0MCA4XHVjZTc4XHVjNzc0IFx1Yzc3NFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL2FzZGYucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk0cHg7IHdpZHRoOjE5OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YyBLbmlnaHRcdWIyOTQgXHVjOTExXHVhYzA0XHVjNWQwIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIzNTRcdWI3N2NcdWIzYzQgXHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgUGF3blx1Yzc0MCBcdWMwYzFcdWIzMDBcdWQzMDBcdWM3NTggXHViOWQwXHVjNzQwIFx1YzdhMVx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MChcdWM5ODksIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc1OCBcdWM1ZWRcdWQ1NjBcdWI5Y2MgXHVkNTVjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNCkuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWI5ZDBcdWM3NzQgXHViYzMwXHVjZTU4XHVhYzAwIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVjOWM0XHVkNTU4XHVhYzhjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyBcdWJkODBcdWJkODRcdWM3NzQgXHVjNTQ4XHVjODA0XHVkNTVjIFx1Y2U3OFx1Yzc3NCBcdWI0MjAgXHVhYzgzXHVjNzc0XHViMmU0LiAoSyA6IEtuaWdodCwgUSA6IFF1ZWVuLCBQIDogUGF3bik8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwN1wvcWF6d3FzengucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgxcHg7IHdpZHRoOjE5NXB4XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2NiNFx1YzJhNCBcdWQzMTBcdWM3NTggXHVkMDZjXHVhZTMwIG5cdWFjZmMgbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxJmx0Oz1uLCBtJmx0Oz0xMDAwKSBcdWFkZjhcdWI5YWNcdWFjZTAgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBRdWVlblx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVhZGY4IFx1YWMxY1x1YzIxOFx1YjljY1x1ZDA3Y1x1Yzc1OCBRdWVlblx1Yzc1OCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHViOWM4XHVjYzJjXHVhYzAwXHVjOWMwXHViODVjIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQ8YnIgXC8+XHJcbktuaWdodFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgXHVjNzA0XHVjZTU4LCBcdWIxMzdcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFBhd25cdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWM3ODVcdWI4MjVcdWI0MWNcdWIyZTQuIChcdWM5ODkgXHViNDU4XHVjOWY4IFx1YzkwNH4gXHViMTM3XHVjOWY4IFx1YzkwNFx1Yzc0MCZuYnNwOyBrLHIxLGMxLHIyLGMyLC4uLixyayxjayBcdWM3NzQgXHViZTQ4XHVjZTc4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIHJpXHViMjk0IGlcdWJjODhcdWM5ZjggXHViOWQwXHVjNzU4IFx1ZDU4OSBcdWM3MDRcdWNlNTgsIGNpXHViMjk0IGlcdWJjODhcdWM5ZjggXHViOWQwXHVjNzU4IFx1YzVmNCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LikgXHVkNTVjIFx1Y2U3OFx1YzVkMFx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHViOWQwXHViOWNjIFx1YjE5M1x1Yzc3OFx1YjJlNFx1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NWNcdWIyZTQuIEtuaWdodCwgUXVlZW4sIFBhd25cdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IFx1YWMwMVx1YWMwMSAxMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG4qbSBcdWNjYjRcdWMyYTRcdWQzMTBcdWM1ZDAgXHVjNTQ4XHVjODA0XHVkNTVjIFx1Y2U3OFx1Yzc3NCBcdWJhODcgXHVjZTc4XHVjNzc4XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTg2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUXVlZW5zLCBLbmlnaHRzIGFuZCBQYXducyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFsbCBhcmUgZmFtaWxpYXIgd2l0aCB0aGUgZmFtb3VzIDgtcXVlZW5zIHByb2JsZW0gd2hpY2ggYXNrcyB5b3UgdG8gcGxhY2UgOCBxdWVlbnMgb24gYSBjaGVzcyBib2FyZCBzbyBubyB0d28gYXR0YWNrIGVhY2ggb3RoZXIuIEluIHRoaXMgcHJvYmxlbSwgeW91IHdpbGwgYmUgZ2l2ZW4gbG9jYXRpb25zIG9mIHF1ZWVucyBhbmQga25pZ2h0cyBhbmQgcGF3bnMgYW5kIGFza2VkIHRvIFx1ZmIwMW5kIGhvdyBtYW55IG9mIHRoZSB1bm9jY3VwaWVkIHNxdWFyZXMgb24gdGhlIGJvYXJkIGFyZSBub3QgdW5kZXIgYXR0YWNrIGZyb20gZWl0aGVyIGEgcXVlZW4gb3IgYSBrbmlnaHQgKG9yIGJvdGgpLiBXZSZyc3F1bztsbCBjYWxsIHN1Y2ggc3F1YXJlcyAmbGRxdW87c2FmZSZyZHF1bzsgc3F1YXJlcy4gSGVyZSwgcGF3bnMgd2lsbCBvbmx5IHNlcnZlIGFzIGJsb2NrZXJzIGFuZCBoYXZlIG5vIGNhcHR1cmluZyBhYmlsaXR5LiBUaGUgYm9hcmQgYmVsb3cgaGFzIDYgc2FmZSBzcXVhcmVzLiAoVGhlIHNoYWRlZCBzcXVhcmVzIGFyZSBzYWZlLik8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9xa3AucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjIwcHg7IHdpZHRoOjIyM3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlJlY2FsbCB0aGF0IGEga25pZ2h0IG1vdmVzIHRvIGFueSB1bm9jY3VwaWVkIHNxdWFyZSB0aGF0IGlzIG9uIHRoZSBvcHBvc2l0ZSBjb3JuZXIgb2YgYSAyeDMgcmVjdGFuZ2xlIGZyb20gaXRzIGN1cnJlbnQgcG9zaXRpb247IGEgcXVlZW4gbW92ZXMgdG8gYW55IHNxdWFyZSB0aGF0IGlzIHZpc2libGUgaW4gYW55IG9mIHRoZSBlaWdodCBob3Jpem9udGFsLCB2ZXJ0aWNhbCwgYW5kIGRpYWdvbmFsIGRpcmVjdGlvbnMgZnJvbSB0aGUgY3VycmVudCBwb3NpdGlvbi4gTm90ZSB0aGF0IHRoZSBtb3ZlbWVudCBvZiBhIHF1ZWVuIGNhbiBiZSBibG9ja2VkIGJ5IGFub3RoZXIgcGllY2UsIHdoaWxlIGEga25pZ2h0JnJzcXVvO3MgbW92ZW1lbnQgY2FuIG5vdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgbXVsdGlwbGUgdGVzdCBjYXNlcy4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBjb25zaXN0IG9mIDQgbGluZXMuIFRoZSBmaXJzdCBsaW5lIHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMgbiBhbmQgbSwgaW5kaWNhdGluZyB0aGUgZGltZW5zaW9ucyBvZiB0aGUgYm9hcmQsIGdpdmluZyByb3dzIGFuZCBjb2x1bW5zLCByZXNwZWN0aXZlbHkuIE5laXRoZXIgaW50ZWdlciB3aWxsIGV4Y2VlZCAxMDAwLiBUaGUgbmV4dCB0aHJlZSBsaW5lcyB3aWxsIGVhY2ggYmUgb2YgdGhlIGZvcm08XC9wPlxyXG5cclxuPHByZT5cclxuayByPHN1Yj4xPFwvc3ViPiBjPHN1Yj4xPFwvc3ViPiByPHN1Yj4yPFwvc3ViPiBjPHN1Yj4yPFwvc3ViPiAmbWlkZG90OyAmbWlkZG90OyAmbWlkZG90OyByPHN1Yj5rPFwvc3ViPiBjPHN1Yj5rPFwvc3ViPjxcL3ByZT5cclxuXHJcbjxwPmluZGljYXRpbmcgdGhlIGxvY2F0aW9uIG9mIHRoZSBxdWVlbnMsIGtuaWdodHMgYW5kIHBhd25zLCByZXNwZWN0aXZlbHkuIFRoZSBudW1iZXJpbmcgb2YgdGhlIHJvd3MgYW5kIGNvbHVtbnMgd2lsbCBzdGFydCBhdCBvbmUuIFRoZXJlIHdpbGwgYmUgbm8gbW9yZSB0aGFuIDEwMCBvZiBhbnkgb25lIHBpZWNlLiBWYWx1ZXMgb2YgbiA9IG0gPSAwIGluZGljYXRlIGVuZCBvZiBpbnB1dC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBzaG91bGQgZ2VuZXJhdGUgb25lIGxpbmUgb2YgdGhlIGZvcm08XC9wPlxyXG5cclxuPHByZT5cclxuQm9hcmQgYiBoYXMgcyBzYWZlIHNxdWFyZXMuPFwvcHJlPlxyXG5cclxuPHA+d2hlcmUgYiBpcyB0aGUgbnVtYmVyIG9mIHRoZSBib2FyZCAoc3RhcnRpbmcgYXQgb25lKSBhbmQgeW91IHN1cHBseSB0aGUgY29ycmVjdCB2YWx1ZSBmb3IgczxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==