Minkowski Sum

A polygon includes every point on its boundary and every point in its interior. In this problem, every polygon satisfies all of the following conditions.

1. For any two points inside the polygon, the entire segment connecting them is also inside the polygon.
2. The polygon has at least three vertices.
3. No three vertices lie on one straight line.

Let A and B be two polygons satisfying these conditions. Choose any point (x1, y1) in A and any point (x2, y2) in B. The shape formed by all possible points (x1 + x2, y1 + y2) is called the Minkowski sum of the two polygons.

Given two polygons, write a program that computes their Minkowski sum. If more than one output polygon satisfies the requirements, output exactly one polygon according to the following priorities. A smaller number means a higher priority.

1. The polygon with the fewest vertices
2. The polygon with the smallest area
3. The polygon whose minimum x-coordinate among all its vertices is smallest
4. The polygon whose minimum y-coordinate among all its vertices is smallest

The first line contains N and M, the numbers of vertices of polygons A and B. (3 <= N, M <= 1,000)

The next N lines contain the vertices of polygon A. The following M lines contain the vertices of polygon B. Each vertex is given as two integers x and y separated by a space, and the vertices are listed in counterclockwise order.

Every coordinate is a non-negative integer not greater than 100,000,000.

On the first line, print the number of vertices of the polygon you computed.

Then print the vertices of the polygon in counterclockwise order, one pair of x and y coordinates per line. The first printed vertex must be a vertex with the smallest x-coordinate. If there is more than one such vertex, print the one with the smallest y-coordinate first.

Hermann Minkowski (18641909) was a Russian mathematician who worked in Germany. He was associated with David Hilbert (18621943), who is known for introducing an axiomatic system to geometry, and together they helped make the University of Gottingen a center of world mathematics. In the twentieth century, the university produced major figures in modern physics such as Max Born, James Franck, Werner Heisenberg, and Max von Laue. Minkowski is also known for discussing four-dimensional spacetime in works such as , contributing to the formation of Einstein's theory of relativity.