시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 234 92 73 43.195%

문제

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

힌트

W3sicHJvYmxlbV9pZCI6IjE5ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjYjRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPm4qbSBcdWQwNmNcdWFlMzBcdWM3NTggXHVjY2I0XHVjMmE0IFx1ZDMxMFx1YWNmYywgXHVjMGMxXHViMzAwXHVkMzAwXHVjNzU4IFF1ZWVuLCBLbmlnaHQsIFBhd25cdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjLCBcdWM1NDhcdWM4MDRcdWQ1NWMgXHVjZTc4XHVjNzc0IFx1YmE4NyBcdWNlNzhcdWM3NzhcdWM5YzAgXHVjMTM4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWM1NDhcdWM4MDRcdWQ1NWMgXHVjZTc4XHVjNzc0XHViNzgwIFx1YjlkMFx1Yzc0MCBcdWFkZjggXHVhY2YzXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWI5ZDBcdWM3NzQgXHVjNzg4XHVjNWI0XHViM2M0IFx1YzdhMVx1ZDc5MCBcdWFjMDBcdWIyYTVcdWMxMzFcdWM3NzQgXHVjNWM2XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1Y2MzOFx1YWNlMFx1Yjg1YyBRdWVlblx1Yzc0MCBcdWFjMDBcdWI4NWMsIFx1YzEzOFx1Yjg1YywgXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjljY1x1ZDA3YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHViOWNlXHVjNzc0IFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWI5Y2NcdWM1N2QgXHVhZGY4IFx1YzkxMVx1YWMwNFx1YzVkMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNzg4XHViMmU0XHViYTc0IFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIEtuaWdodFx1YjI5NCAyKjMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWRmOFx1YjgzOFx1Yzc0NCBcdWI1NGMsIFx1YmMxOFx1YjMwMFx1Y2FiZCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1Yzc0MCA4XHVjZTc4XHVjNzc0IFx1Yzc3NFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL2FzZGYucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk0cHg7IHdpZHRoOjE5OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMgS25pZ2h0XHViMjk0IFx1YzkxMVx1YWMwNFx1YzVkMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNzg4XHViMzU0XHViNzdjXHViM2M0IFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFBhd25cdWM3NDAgXHVjMGMxXHViMzAwXHVkMzAwXHVjNzU4IFx1YjlkMFx1Yzc0MCBcdWM3YTFcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAoXHVjOTg5LCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NTggXHVjNWVkXHVkNTYwXHViOWNjIFx1ZDU1Y1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQpLjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViOWQwXHVjNzc0IFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViYTc0IFx1YzljNFx1ZDU1OFx1YWM4YyBcdWQ0NWNcdWMyZGNcdWI0MWMgXHViZDgwXHViZDg0XHVjNzc0IFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWNlNzhcdWM3NzQgXHViNDIwIFx1YWM4M1x1Yzc3NFx1YjJlNC4gKEsgOiBLbmlnaHQsIFEgOiBRdWVlbiwgUCA6IFBhd24pPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDdcL3Fhendxc3p4LnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4MXB4OyB3aWR0aDoxOTVweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNjYjRcdWMyYTQgXHVkMzEwXHVjNzU4IFx1ZDA2Y1x1YWUzMCBuXHVhY2ZjIG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsdDs9biwgbSZsdDs9MTAwMCkgXHVhZGY4XHViOWFjXHVhY2UwIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgUXVlZW5cdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YWRmOCBcdWFjMWNcdWMyMThcdWI5Y2NcdWQwN2NcdWM3NTggUXVlZW5cdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0PGJyIFwvPlxyXG5LbmlnaHRcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzcwNFx1Y2U1OCwgXHViMTM3XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBQYXduXHVjNzU4IFx1YWMxY1x1YzIxOFx1YzY0MCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiAoXHVjOTg5IFx1YjQ1OFx1YzlmOCBcdWM5MDR+IFx1YjEzN1x1YzlmOCBcdWM5MDRcdWM3NDAmbmJzcDsgayxyMSxjMSxyMixjMiwuLi4scmssY2sgXHVjNzc0IFx1YmU0OFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyByaVx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YjlkMFx1Yzc1OCBcdWQ1ODkgXHVjNzA0XHVjZTU4LCBjaVx1YjI5NCBpXHViYzg4XHVjOWY4IFx1YjlkMFx1Yzc1OCBcdWM1ZjQgXHVjNzA0XHVjZTU4XHViOTdjIFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC4pIFx1ZDU1YyBcdWNlNzhcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjlkMFx1YjljYyBcdWIxOTNcdWM3NzhcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LiBLbmlnaHQsIFF1ZWVuLCBQYXduXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWFjMDFcdWFjMDEgMTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuKm0gXHVjY2I0XHVjMmE0XHVkMzEwXHVjNWQwIFx1YzU0OFx1YzgwNFx1ZDU1YyBcdWNlNzhcdWM3NzQgXHViYTg3IFx1Y2U3OFx1Yzc3OFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTk4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1ZWVucywgS25pZ2h0cyBhbmQgUGF3bnMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhbGwgYXJlIGZhbWlsaWFyIHdpdGggdGhlIGZhbW91cyA4LXF1ZWVucyBwcm9ibGVtIHdoaWNoIGFza3MgeW91IHRvIHBsYWNlIDggcXVlZW5zIG9uIGEgY2hlc3MgYm9hcmQgc28gbm8gdHdvIGF0dGFjayBlYWNoIG90aGVyLiBJbiB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIGJlIGdpdmVuIGxvY2F0aW9ucyBvZiBxdWVlbnMgYW5kIGtuaWdodHMgYW5kIHBhd25zIGFuZCBhc2tlZCB0byBcdWZiMDFuZCBob3cgbWFueSBvZiB0aGUgdW5vY2N1cGllZCBzcXVhcmVzIG9uIHRoZSBib2FyZCBhcmUgbm90IHVuZGVyIGF0dGFjayBmcm9tIGVpdGhlciBhIHF1ZWVuIG9yIGEga25pZ2h0IChvciBib3RoKS4gV2UmcnNxdW87bGwgY2FsbCBzdWNoIHNxdWFyZXMgJmxkcXVvO3NhZmUmcmRxdW87IHNxdWFyZXMuIEhlcmUsIHBhd25zIHdpbGwgb25seSBzZXJ2ZSBhcyBibG9ja2VycyBhbmQgaGF2ZSBubyBjYXB0dXJpbmcgYWJpbGl0eS4gVGhlIGJvYXJkIGJlbG93IGhhcyA2IHNhZmUgc3F1YXJlcy4gKFRoZSBzaGFkZWQgc3F1YXJlcyBhcmUgc2FmZS4pPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcWtwLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIyMHB4OyB3aWR0aDoyMjNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5SZWNhbGwgdGhhdCBhIGtuaWdodCBtb3ZlcyB0byBhbnkgdW5vY2N1cGllZCBzcXVhcmUgdGhhdCBpcyBvbiB0aGUgb3Bwb3NpdGUgY29ybmVyIG9mIGEgMngzIHJlY3RhbmdsZSBmcm9tIGl0cyBjdXJyZW50IHBvc2l0aW9uOyBhIHF1ZWVuIG1vdmVzIHRvIGFueSBzcXVhcmUgdGhhdCBpcyB2aXNpYmxlIGluIGFueSBvZiB0aGUgZWlnaHQgaG9yaXpvbnRhbCwgdmVydGljYWwsIGFuZCBkaWFnb25hbCBkaXJlY3Rpb25zIGZyb20gdGhlIGN1cnJlbnQgcG9zaXRpb24uIE5vdGUgdGhhdCB0aGUgbW92ZW1lbnQgb2YgYSBxdWVlbiBjYW4gYmUgYmxvY2tlZCBieSBhbm90aGVyIHBpZWNlLCB3aGlsZSBhIGtuaWdodCZyc3F1bztzIG1vdmVtZW50IGNhbiBub3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIG11bHRpcGxlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIHdpbGwgY29uc2lzdCBvZiA0IGxpbmVzLiBUaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzIG4gYW5kIG0sIGluZGljYXRpbmcgdGhlIGRpbWVuc2lvbnMgb2YgdGhlIGJvYXJkLCBnaXZpbmcgcm93cyBhbmQgY29sdW1ucywgcmVzcGVjdGl2ZWx5LiBOZWl0aGVyIGludGVnZXIgd2lsbCBleGNlZWQgMTAwMC4gVGhlIG5leHQgdGhyZWUgbGluZXMgd2lsbCBlYWNoIGJlIG9mIHRoZSBmb3JtPFwvcD5cclxuXHJcbjxwcmU+XHJcbmsgcjxzdWI+MTxcL3N1Yj4gYzxzdWI+MTxcL3N1Yj4gcjxzdWI+MjxcL3N1Yj4gYzxzdWI+MjxcL3N1Yj4gJm1pZGRvdDsgJm1pZGRvdDsgJm1pZGRvdDsgcjxzdWI+azxcL3N1Yj4gYzxzdWI+azxcL3N1Yj48XC9wcmU+XHJcblxyXG48cD5pbmRpY2F0aW5nIHRoZSBsb2NhdGlvbiBvZiB0aGUgcXVlZW5zLCBrbmlnaHRzIGFuZCBwYXducywgcmVzcGVjdGl2ZWx5LiBUaGUgbnVtYmVyaW5nIG9mIHRoZSByb3dzIGFuZCBjb2x1bW5zIHdpbGwgc3RhcnQgYXQgb25lLiBUaGVyZSB3aWxsIGJlIG5vIG1vcmUgdGhhbiAxMDAgb2YgYW55IG9uZSBwaWVjZS4gVmFsdWVzIG9mIG4gPSBtID0gMCBpbmRpY2F0ZSBlbmQgb2YgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RWFjaCB0ZXN0IGNhc2Ugc2hvdWxkIGdlbmVyYXRlIG9uZSBsaW5lIG9mIHRoZSBmb3JtPFwvcD5cclxuXHJcbjxwcmU+XHJcbkJvYXJkIGIgaGFzIHMgc2FmZSBzcXVhcmVzLjxcL3ByZT5cclxuXHJcbjxwPndoZXJlIGIgaXMgdGhlIG51bWJlciBvZiB0aGUgYm9hcmQgKHN0YXJ0aW5nIGF0IG9uZSkgYW5kIHlvdSBzdXBwbHkgdGhlIGNvcnJlY3QgdmFsdWUgZm9yIHM8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=