Find Minimal Axial Symmetry Transformations

Given two sets of n points in the plane, \(A_1, A_2, \ldots, A_n\) and \(B_1, B_2, \ldots, B_n\), where the point \(B_i\) is obtained by applying a sequence of axial (line) reflections to \(A_i\) (for \(i=1,2,\dots,n\)), find a sequence of valid reflection transformations that transforms every \(A_i\) into \(B_i\). In other words, determine a sequence of reflection operations whose composition is the unique isometry \(T\) satisfying \(T(A_i)=B_i\) for all \(i\). The goal is to use as few reflection steps as possible.

It is known that any isometry can be represented as:

• Zero reflections if \(T\) is the identity,
• One reflection if \(T\) is itself a reflection, and
• Two reflections otherwise (which covers both rotations and translations).

You are given the coordinates of \(A_i=(x_i,y_i)\) and \(B_i=(x'_i,y'_i)\) with \(i=1,2,\dots,n\). If the isometry \(T\) turns out to be a translation, you can represent it as a composition of two reflections in parallel lines; if it is a rotation, it can be decomposed as two reflections in intersecting lines. When the transformation is a reflection, its mirror line is the perpendicular bisector of any segment \(A_jB_j\) (for any index \(j\) with \(A_j\neq B_j\)).

Reflection Operation Format: A reflection with respect to a line \(ax+by+c=0\) transforms any point \(P=(x,y)\) into

[ P' = \left(x - \frac{2(a,x+b,y+c)a}{a^2+b^2},; y - \frac{2(a,x+b,y+c)b}{a^2+b^2}\right). ]

Your task is to output the number of reflection steps followed by the parameters \(a, b, c\) for each reflection line (one per line) that yield a correct transformation \(T\) with as few steps as possible. If \(T\) is the identity, output 0.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)). The next \(n\) lines each contain two space‐separated numbers \(x_i\) and \(y_i\), representing the coordinates of \(A_i\). The following \(n\) lines each contain two space‐separated numbers \(x'_i\) and \(y'_i\), representing the coordinates of \(B_i\). All coordinates are real numbers.

outputFormat

On the first line, output an integer \(k\) representing the minimal number of reflection steps (which will be 0, 1, or 2). Then, output \(k\) lines. Each line should contain three space‐separated real numbers \(a, b, c\) which represent the line \(ax+by+c=0\) used for that reflection.

The output transformation must satisfy that applying the reflections in the order given to every \(A_i\) yields \(B_i\) for all \(i=1,\dots,n\), with an absolute or relative error of at most \(10^{-6}\).

sample

2
0 0
1 1
0 0
1 1

0