위험 구역 탈출

세준이는 격자판에서 탈출하는 게임을 하고 있다. 각 칸은 세 종류 중 하나이다. 안전한 칸은 생명을 잃지 않고 들어갈 수 있고, 위험한 칸에 들어가면 생명이 1 줄어든다. 죽음의 칸에는 들어갈 수 없다.

세준이는 (0, 0)에서 시작해 (500, 500)까지 이동해야 한다. 한 번에 위, 아래, 왼쪽, 오른쪽으로 한 칸씩만 움직일 수 있으며, 좌표가 0 이상 500 이하인 게임판 밖으로 나갈 수 없다.

시작 칸이 위험한 칸이거나 죽음의 칸이어도 이미 그 칸에 서 있으므로 시작할 때 생명은 줄지 않고, 시작 자체도 막히지 않는다. 이동해서 어떤 칸에 들어갈 때만 그 칸의 효과가 적용된다.

목적지까지 갈 때 잃는 생명의 최솟값을 구하라.

첫째 줄에 위험한 구역의 수 N이 주어진다. 이어지는 N개 줄에는 위험한 구역을 나타내는 네 정수 X1 Y1 X2 Y2가 주어진다. (X1, Y1)과 (X2, Y2)는 좌표축에 평행한 직사각형 구역의 서로 반대쪽 꼭짓점이다.

그다음 줄에 죽음의 구역의 수 M이 주어진다. 이어지는 M개 줄에는 죽음의 구역도 같은 형식으로 주어진다.

모든 구역은 경계 위의 칸도 포함한다. 여러 구역이 겹치면 더 심한 구역이 적용된다. 죽음의 구역은 위험한 구역보다 우선하고, 위험한 구역은 안전한 칸보다 우선한다. 위험한 구역이 여러 번 겹쳐도 그 칸에 들어갈 때 잃는 생명은 1이다.

0 <= N, M <= 50이고, 모든 좌표는 0 이상 500 이하의 정수이다.

첫째 줄에 (0, 0)에서 (500, 500)까지 이동하며 잃는 생명의 최솟값을 출력한다. 갈 수 없다면 -1을 출력한다.