Mall Mania

Waterloo has two giant shopping malls, each enclosing several city blocks. Kim and Pat like to shop and to walk within the malls, but they dislike walking between the malls, because such walking does not contribute directly to the task at hand: shopping. They would therefore like to know the minimum crossing distance between the two malls.

Each city block is a unit square delimited by streets and avenues. Streets run east–west and avenues run north–south, and both are identified by consecutive integers from $0$ to $2000$: lower-numbered avenues lie west of higher-numbered avenues, and lower-numbered streets lie south of higher-numbered streets. Streets and avenues are narrow, so their thickness may be assumed to be $0$.

Each mall is a contiguous set of complete city blocks. Contiguous means that any two of its blocks are joined by a sequence of blocks in which consecutive blocks share a side. The two malls do not overlap and do not surround any empty block; that is, the blocks belonging to no mall are themselves contiguous.

Because Kim and Pat always walk along streets and avenues, the walking distance between two intersections $(a_1, s_1)$ and $(a_2, s_2)$ is $|a_1 - a_2| + |s_1 - s_2|$.

The input contains several test cases. Each test case describes the two malls.

A mall's description begins with an integer $p \ge 4$, the perimeter of the mall, followed by $p$ coordinate pairs $(a, s)$ — spread over one or more lines — giving, in clockwise order, the coordinates of the avenue–street intersections that lie on the mall's boundary. (Consecutive listed intersections are one unit apart, so the $p$ pairs are exactly the lattice points along the boundary.)

The two mall descriptions of a test case are given one after another. A line containing a single $0$ follows the last test case.

For each test case, output a single line containing one integer $d$: the minimum walking distance between the two malls, measured along streets and avenues.