시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 38 10 4 40.000%

문제

일요일을 맞이해 창영이는 집안의 모든 침대 시트를 빨고, 집 앞 잔디밭에서 말리고 있다. 갑자기, 엄청난 강풍이 몰아쳤고 모든 침대 시트는 땅바닥에 떨어지게 되었다.

잔디밭은 크기가 무한대인 정사각형 격자로 나타낼 수 있고, 각 단위 정사각형은 좌표 쌍으로 나타낼 수 있다. 침대 시트는 직사각형이며, 축에 평행하다. 시트는 서로 겹칠 수도 있다.

다시 빨래줄에 시트를 걸어놓기 위해 창영이는 막대를 (0,0)에 꽂았다. 그런데 갑자기 땅에서 기름이 나오기 시작했다. 창영이는 이런 예상하지 못한 상황에 당황하였고 결국 기절했다. 창영이가 기절한 사이에 기름은 퍼져나갔다.

시간은 기름이 퍼지기 시작한 순간부터 측정하기 시작한다. 가장 처음에는 단위 정사각형 (0,0)만 기름이 있다. 기름은 아래 그림에 나와있는 것 같이 1초에 한 정사각형씩 여덟 방향으로 이동한다. 기름이 단위 정사각형에 들어가게 되면, 즉시 그 정사각형을 가득 채우게 되고, 그 부분에 속해있는 시트에도 기름이 스며들게 된다.

시간 0, 1, 2초의 모습이다.

입력으로 주어지는 시간이 지난 후에 기름이 물들은 시트의 면적을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 침대 시트의 수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개 줄에는 침대 시트를 나타내는 좌표 x1, y1, x2, y2가 주어진다. (x1, y1), (x2, y2)는 침대 시트의 양 끝 대각선 좌표이다. 이 좌표는 좌표평면 위의 점이 아닌 각 단위 정사각형을 나타낸다. (0, 0)을 포함하는 침대 시트는 없다.

다음 줄에는 시간의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개 줄에는 시간이 주어진다. 이 정수는 0과 1,000,000 사이의 정수이다. 오름차순으로 주어진다.

출력

각각의 시간에 대해서, 기름에 물들은 침대 시트 영역의 크기를 출력한다.

예제 입력 1

3
-2 1 1 2
1 0 2 1
-3 -3 -2 0
2
1 2

예제 출력 1

5
15
W3sicHJvYmxlbV9pZCI6IjI5MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJlNjhcdWI3YWJcdWM5MDQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3Y1x1YzY5NFx1Yzc3Y1x1Yzc0NCBcdWI5ZGVcdWM3NzRcdWQ1NzQgXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1YzlkMVx1YzU0OFx1Yzc1OCBcdWJhYThcdWI0ZTAgXHVjZTY4XHViMzAwIFx1YzJkY1x1ZDJiOFx1Yjk3YyBcdWJlNjhcdWFjZTAsIFx1YzlkMSBcdWM1NWUgXHVjNzk0XHViNTE0XHViYzJkXHVjNWQwXHVjMTFjIFx1YjlkMFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWMxMVx1Yzc5MFx1YWUzMCwgXHVjNWM0XHVjY2FkXHViMDljIFx1YWMxNVx1ZDQ4ZFx1Yzc3NCBcdWJhYjBcdWM1NDRcdWNjZTRcdWFjZTAgXHViYWE4XHViNGUwIFx1Y2U2OFx1YjMwMCBcdWMyZGNcdWQyYjhcdWIyOTQgXHViNTQ1XHViYzE0XHViMmU1XHVjNWQwIFx1YjVhOFx1YzViNFx1YzljMFx1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5NFx1YjUxNFx1YmMyZFx1Yzc0MCBcdWQwNmNcdWFlMzBcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWFjYTlcdWM3OTBcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWIyZThcdWM3MDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1Yzg4Y1x1ZDQ1YyBcdWMzMGRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Y2U2OFx1YjMwMCBcdWMyZGNcdWQyYjhcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViYTcwLCBcdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHViMmU0LiBcdWMyZGNcdWQyYjhcdWIyOTQgXHVjMTFjXHViODVjIFx1YWNiOVx1Y2U2MCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWMyZGMgXHViZTY4XHViNzk4XHVjOTA0XHVjNWQwIFx1YzJkY1x1ZDJiOFx1Yjk3YyBcdWFjNzhcdWM1YjRcdWIxOTNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWI5YzlcdWIzMDBcdWI5N2MgKDAsMClcdWM1ZDAgXHVhZjQyXHVjNTU4XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhYzExXHVjNzkwXHVhZTMwIFx1YjU0NVx1YzVkMFx1YzExYyBcdWFlMzBcdWI5ODRcdWM3NzQgXHViMDk4XHVjNjI0XHVhZTMwIFx1YzJkY1x1Yzc5MVx1ZDU4OFx1YjJlNC4gXHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IFx1Yzc3NFx1YjdmMCBcdWM2MDhcdWMwYzFcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjIFx1YzBjMVx1ZDY2OVx1YzVkMCBcdWIyZjlcdWQ2NjlcdWQ1NThcdWM2MDBcdWFjZTAgXHVhY2IwXHVhZDZkIFx1YWUzMFx1YzgwOFx1ZDU4OFx1YjJlNC4gXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1YWUzMFx1YzgwOFx1ZDU1YyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVhZTMwXHViOTg0XHVjNzQwIFx1ZDM3Y1x1YzgzOFx1YjA5OFx1YWMxNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhYzA0XHVjNzQwIFx1YWUzMFx1Yjk4NFx1Yzc3NCBcdWQzN2NcdWM5YzBcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTVjIFx1YzIxY1x1YWMwNFx1YmQ4MFx1ZDEzMCBcdWNlMjFcdWM4MTVcdWQ1NThcdWFlMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwXHViMjk0IFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgKDAsMClcdWI5Y2MgXHVhZTMwXHViOTg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVhZTMwXHViOTg0XHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1YWM4MyBcdWFjMTlcdWM3NzQgMVx1Y2QwOFx1YzVkMCBcdWQ1NWMgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNTI5IFx1YzVlY1x1YjM1ZiBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWFlMzBcdWI5ODRcdWM3NzQgXHViMmU4XHVjNzA0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWFjOGMgXHViNDE4XHViYTc0LCBcdWM5ODlcdWMyZGMgXHVhZGY4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWFjMDBcdWI0ZGQgXHVjYzQ0XHVjNmIwXHVhYzhjIFx1YjQxOFx1YWNlMCwgXHVhZGY4IFx1YmQ4MFx1YmQ4NFx1YzVkMCBcdWMxOGRcdWQ1NzRcdWM3ODhcdWIyOTQgXHVjMmRjXHVkMmI4XHVjNWQwXHViM2M0IFx1YWUzMFx1Yjk4NFx1Yzc3NCBcdWMyYTRcdWJhNzBcdWI0ZTRcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL29pbCgxKS5wbmdcIiBzdHlsZT1cImhlaWdodDoxODBweDsgd2lkdGg6NjE3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjMmRjXHVhYzA0IDAsIDEsIDJcdWNkMDhcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM5YzBcdWIwOWMgXHVkNmM0XHVjNWQwIFx1YWUzMFx1Yjk4NFx1Yzc3NCBcdWJiM2NcdWI0ZTRcdWM3NDAgXHVjMmRjXHVkMmI4XHVjNzU4IFx1YmE3NFx1YzgwMVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZTY4XHViMzAwIFx1YzJkY1x1ZDJiOFx1Yzc1OCBcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWNlNjhcdWIzMDAgXHVjMmRjXHVkMmI4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4OGNcdWQ0NWMgeDEsIHkxLCB4MiwgeTJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoeDEsIHkxKSwgKHgyLCB5MilcdWIyOTQgXHVjZTY4XHViMzAwIFx1YzJkY1x1ZDJiOFx1Yzc1OCBcdWM1OTEgXHViMDVkIFx1YjMwMFx1YWMwMVx1YzEyMCBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjODhjXHVkNDVjXHVkM2M5XHViYTc0IFx1YzcwNFx1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YWMwMSBcdWIyZThcdWM3MDQgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC4gKDAsIDApXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWNlNjhcdWIzMDAgXHVjMmRjXHVkMmI4XHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NTggXHVhYzFjXHVjMjE4IE0gKDEgJmxlOyBNICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzgxNVx1YzIxOFx1YjI5NCAwXHVhY2ZjIDEsMDAwLDAwMCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFlMzBcdWI5ODRcdWM1ZDAgXHViYjNjXHViNGU0XHVjNzQwIFx1Y2U2OFx1YjMwMCBcdWMyZGNcdWQyYjggXHVjNjAxXHVjNWVkXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkyOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBMQUhURSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gd2FzaGVkIGhpcyBzaGVldHMgYW5kIGlzIG9uIGhpcyB3YXkgdG8gaGFuZyB0aGVtIHRvIGRyeSBpbiBmcm9udCBvZiBoaXMgaG91c2UuIEhvd2V2ZXIsIHN0cm9uZyB3aW5kcyBoYXZlIHB1bGxlZCB0aGUgY2xvdGhlc2xpbmUgb3V0IG9mIHRoZSBncm91bmQgc28gTWlya28gdGVtcG9yYXJpbHkgbGFpZCBvdXQgdGhlIHNoZWV0cyBvbiB0aGUgZ3Jhc3MuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBncmFzcyBmaWVsZCBjYW4gYmUgbW9kZWxlZCBieSBhbiBpbmZpbml0ZSBzcXVhcmUgZ3JpZCwgd2hlcmUgZXZlcnkgdW5pdCBzcXVhcmUgaXMgcmVwcmVzZW50ZWQgYnkgYSBwYWlyIG9mIGNvb3JkaW5hdGVzLiBTaGVldHMgYXJlIHJlY3RhbmdsZXMgaW4gdGhlIGdyaWQgd2l0aCBzaWRlcyBwYXJhbGxlbCB0byB0aGUgY29vcmRpbmF0ZSBheGVzLiBTaGVldHMgbWF5IG92ZXJsYXAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIGFuIGVmZm9ydCB0byBwdXQgaGlzIGNsb3RoZXNsaW5lIGJhY2sgdXAsIE1pcmtvIHNsYW1tZWQgYSBwb2xlIGludG8gdGhlIGdyb3VuZCBhdCBjb29yZGluYXRlcyAoMCwgMCkuIEFuIGVudGlyZWx5IHVuZXhwZWN0ZWQgdHVybiBvZiBldmVudHMgZm9sbG93ZWQuIE9pbCBzcHJ1bmcgZnJvbSB0aGUgZ3JvdW5kIGFuZCB0aGUgc2hvY2sgY2F1c2VkIE1pcmtvIHRvIGZhaW50LiBXaGlsZSBNaXJrbyBsYXkgdW5jb25zY2lvdXMsIHRoZSBvaWwgaXMgc3ByZWFkaW5nLCBzdGFpbmluZyBoaXMgc2hlZXRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaW1lIGlzIG1lYXN1cmVkIGZyb20gdGhlIG1vbWVudCB0aGUgb2lsIHN0YXJ0cyBzcHJlYWRpbmcgJm5kYXNoOyBhdCB0aW1lIHplcm8gb25seSBzcXVhcmUgKDAsIDApIGlzIGNvdmVyZWQgaW4gb2lsLiBUaGUgb2lsIGlzIHNwcmVhZGluZyBhdCBhIHNwZWVkIG9mIG9uZSBzcXVhcmUgcGVyIHNlY29uZCBpbiBhbGwgZWlnaHQgZGlyZWN0aW9ucywgYXMgc2hvd24gaW4gdGhlIGZpZ3VyZSBiZWxvdy4gV2hlbiBvaWwgZW50ZXJzIGEgc3F1YXJlLCBpdCBzdGFpbnMgdGhhdCBzcXVhcmUgb2YgZmFicmljIG9uIGFsbCBzaGVldHMgY292ZXJpbmcgdGhlIHNxdWFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9vaWwoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTgwcHg7IHdpZHRoOjYxN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBncmFzcyBmaWVsZCBmcm9tIHRoZSBmaXJzdCBleGFtcGxlIGFmdGVyIHplcm8sIG9uZSBhbmQgdHdvIHNlY29uZHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiBNIHBvaW50cyBpbiB0aW1lLCBjYWxjdWxhdGVzIHRoZSB0b3RhbCBhcmVhIG9mIHN0YWluZWQgZmFicmljIG9uIGFsbCBzaGVldHMgZm9yIGVhY2ggb2YgdGhlIGdpdmVuIHRpbWUgcG9pbnRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHNoZWV0cy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgZm91ciBpbnRlZ2VycyB4MSwgeTEsIHgyIGFuZCB5MiAoJm1pbnVzOzEgMDAwIDAwMCAmbGU7IHgxICZsZTsgeDIgJmxlOyAxIDAwMCAwMDApLCAoJm1pbnVzOzEgMDAwIDAwMCAmbGU7IHkxICZsZTsgeTIgJmxlOyAxIDAwMCAwMDApLiBUaGUgY29vcmRpbmF0ZXMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIHJlcHJlc2VudCBkaWFnb25hbGx5IG9wcG9zaXRlIGNvcm5lcnMgb2YgYSBzaGVldCAoYWdhaW4sIHRoZXNlIGNvb3JkaW5hdGVzIGFyZSB1bml0IHNxdWFyZXMsIG5vdCBwb2ludHMgb24gdGhlIHBsYW5lKS4gTm9uZSBvZiB0aGUgc2hlZXRzIHdpbGwgY292ZXIgdGhlIHNxdWFyZSAoMCwgMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBNICgxICZsZTsgTSAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHBvaW50cyBpbiB0aW1lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnRhaW5zIE0gaW50ZWdlcnMgYmV0d2VlbiAwIGFuZCAxIDAwMCAwMDAsIHRoZSB0aW1lIHBvaW50cy4gVGhleSB3aWxsIGJlIGdpdmVuIGluIHN0cmljdGx5IGFzY2VuZGluZyBvcmRlci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBvZiB0aGUgdGltZSBwb2ludHMsIG91dHB1dCBvbiBhIHNlcGFyYXRlIGxpbmUgdGhlIHRvdGFsIGFyZWEgb2Ygc3RhaW5lZCBmYWJyaWMgb24gYWxsIHNoZWV0cywgaW4gdGhlIG9yZGVyIHRoZSB0aW1lIHBvaW50cyBhcmUgZ2l2ZW4gaW4gdGhlIGlucHV0LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==