빨랫줄

일요일을 맞아 창영이는 집안의 모든 침대 시트를 빨아 집 앞 잔디밭에서 말리고 있었다. 그런데 갑자기 강한 바람이 불어 모든 침대 시트가 땅에 떨어졌다.

잔디밭은 무한히 큰 정사각형 격자로 볼 수 있으며, 각 단위 정사각형은 정수 좌표쌍 (x, y)로 나타낸다. 침대 시트는 좌표축에 평행한 직사각형이고, 서로 겹칠 수 있다.

창영이는 시트를 다시 빨랫줄에 걸기 위해 막대를 (0, 0)에 꽂았다. 그 순간 땅에서 기름이 나오기 시작했고, 창영이는 놀라 기절했다. 창영이가 기절해 있는 동안 기름은 계속 퍼져 나갔다.

시간은 기름이 퍼지기 시작한 순간부터 잰다. 처음에는 단위 정사각형 (0, 0)에만 기름이 있다. 기름은 아래 그림처럼 1초마다 여덟 방향으로 한 칸씩 퍼진다. 기름이 어떤 단위 정사각형에 들어가면 그 칸 전체가 즉시 기름으로 채워지고, 그 칸에 놓인 시트도 기름에 젖는다.

그림은 시간 0초, 1초, 2초의 모습을 보여준다. 주어진 각 시간이 지난 뒤, 기름에 젖은 침대 시트의 총넓이를 구하라. 서로 겹친 부분은 그 부분을 덮는 시트의 개수만큼 넓이에 더한다.

첫째 줄에 침대 시트의 수 N이 주어진다. 1 <= N <= 100000.

다음 N개 줄에는 침대 시트를 나타내는 네 정수 x1 y1 x2 y2가 주어진다. -1000000 <= x1 <= x2 <= 1000000, -1000000 <= y1 <= y2 <= 1000000이다. (x1, y1)과 (x2, y2)는 시트가 덮는 두 대각선 단위 정사각형의 좌표이며, 좌표평면 위의 점이 아니다. (0, 0)을 포함하는 침대 시트는 주어지지 않는다.

다음 줄에 시간의 개수 M이 주어진다. 1 <= M <= 100000.

다음 M개의 정수는 질의 시간이다. 각 시간은 0 이상 1000000 이하이며, 오름차순으로 주어지고 중복되지 않는다.

각 질의 시간마다, 그 시간이 지난 뒤 기름에 젖은 침대 시트 영역의 넓이를 한 줄에 하나씩 출력한다.