Equivalent Knight Moves

A knight moves on an infinite chessboard. Every move of the knight is described by a pair of integers \( (a,b) \). A move \( (a,b) \) means that the knight can move from a cell \( (x,y) \) to either \( (x+a, y+b) \) or \( (x-a, y-b) \). Each knight is given a set of such moves; it is guaranteed that the set of cells reachable from \( (0,0) \) is not collinear. We say that two knights are equivalent if they can reach exactly the same set of squares starting from \( (0,0) \).

One can show that for every knight there exists a unique canonical representation of its move set by a pair of moves. In particular, if a knight is given by two (non‐collinear) moves \( v_1=(x_1,y_1) \) and \( v_2=(x_2,y_2) \), then one may compute its Hermite Normal Form (HNF) basis, which is unique and has the form:

[ \begin{pmatrix} h & r \ 0 & s \end{pmatrix}, \quad\text{with } h>0,\ s>0\text{ and } 0\le r<s. ]

Your task is to read two knights’ move representations (each given by two moves) and compute for each the unique canonical basis of the lattice of reachable squares. If the two knights are equivalent then these canonical representations will be identical. Output the two canonical representations as two pairs of moves in the following order: for each knight output four integers: h 0 r s (note that the first move is always of the form \( (h,0) \)) separated by spaces.

Hint: For a knight with moves \( v_1=(x_1,y_1) \) and \( v_2=(x_2,y_2) \), you may do the following:

• Compute \( h = \gcd(x_1, x_2) \). (Since the moves are non‐collinear, \( h>0 \))
• Compute the absolute value of the determinant: \( \Delta=|x_1y_2-x_2y_1| \).
• Then \( s = \Delta/h \) (it is guaranteed that \( h \) divides \( \Delta \)).
• Find integers \( u,v \) (by the extended Euclidean algorithm) such that \( u \cdot x_1+ v\cdot x_2 = h \).
• Compute \( r = (u\cdot y_1+v\cdot y_2) \mod s \) (with \( 0\le r<s \)).

Then the canonical representation (HNF basis) is given by the two moves: \( (h,0) \) and \( (r,s) \).

inputFormat

The input consists of two lines. Each line contains four space‐separated integers. The first line represents the two moves of the first knight: x1 y1 x2 y2, and the second line contains x3 y3 x4 y4 for the second knight. It is guaranteed that in each line, the two moves are non‐collinear.

outputFormat

Output a single line containing eight space‐separated integers. The first four integers represent the canonical basis of the first knight in the form h 0 r s, and the next four represent the canonical basis of the second knight in the same form. If the two knights are equivalent then the two canonical representations will be identical.

sample

2 1 1 2
2 1 1 2

1 0 2 3 1 0 2 3