Equivalent Knight Moves

A knight moves on an infinite chessboard. Each move it can make is described by a pair of integers: a pair $(a, b)$ means that from a square $(x, y)$ the knight can jump to $(x+a, y+b)$ or to $(x-a, y-b)$. Every knight has a fixed set of such pairs. For each knight we assume that the squares reachable from $(0, 0)$ in a single move are not all collinear.

Two knights are called equivalent if, starting from $(0, 0)$, they can reach exactly the same set of squares (using any number of moves). Equivalent knights may need a different number of moves to reach a given square. It can be shown that for every knight there is an equivalent one whose moves are described by just two pairs of integers.

The set of squares a knight can reach from $(0, 0)$ is exactly the integer lattice generated by its move vectors. Two knights are therefore equivalent if and only if their move vectors generate the same lattice, so this problem asks you to find a two-vector basis of that lattice. Because such a basis is not unique, you must output the single canonical basis defined below.

Given the knight's move pairs, output the two pairs $(a, b)$ and $(c, d)$ that form the Hermite Normal Form (HNF) basis of the generated lattice: the unique pair of vectors that generate the same lattice as the input moves and satisfy

• $c = 0$,
• $a > 0$ and $d > 0$,
• $0 \le b < d$.

This canonical basis always exists and is unique.

The first line contains one integer $n$, the number of pairs describing the knight's moves ($3 \le n \le 100$). Each of the next $n$ lines contains two integers $a_i$ and $b_i$ separated by a single space ($-100 \le a_i, b_i \le 100$, $(a_i, b_i) \ne (0, 0)$). The vectors are guaranteed not to be all collinear.

Print two lines. The first line contains two integers $a$ and $b$ (the first HNF vector); the second line contains two integers $c$ and $d$ (the second HNF vector), each pair separated by a single space. By definition $c = 0$, $a > 0$, $d > 0$ and $0 \le b < d$. This canonical basis is unique and generates the same lattice, hence describes a knight equivalent to the one in the input. It is guaranteed that $1 \le a \le 100$ and $1 \le d \le 20000$.