Escape the Hazard Zones

Sejun is playing an escape game on a grid. Each cell is one of three types. A safe cell can be entered without losing life. Entering a dangerous cell costs 1 life. A death cell cannot be entered.

Sejun starts at (0, 0) and must reach (500, 500). Each move goes exactly one cell up, down, left, or right. He cannot leave the board, whose coordinates are between 0 and 500, inclusive.

If the starting cell is dangerous or a death cell, it has no effect because Sejun is already standing there. Cell effects apply only when he moves into a cell.

Find the minimum amount of life Sejun must lose to reach the destination.

The first line contains N, the number of dangerous zones. Each of the next N lines contains four integers X1 Y1 X2 Y2 describing one dangerous zone. (X1, Y1) and (X2, Y2) are opposite corners of an axis-aligned rectangle.

The next line contains M, the number of death zones. Each of the next M lines describes a death zone in the same format.

All zones include their boundary cells. Zones may overlap; the more severe type applies. Death zones override dangerous zones, and dangerous zones override safe cells. Even if several dangerous zones overlap on the same cell, entering that cell costs only 1 life.

0 <= N, M <= 50, and every coordinate is an integer between 0 and 500, inclusive.

Print the minimum life lost while moving from (0, 0) to (500, 500). If the destination cannot be reached, print -1.