23583번 - Lui and Lines 다국어

Lui is a magician, and recently he mastered traveling in $n$-dimensional space. In order to adjust the settings of his new multidimensional spaceship, he has to find the distance between two lines in $n$-dimensional space. Each line is defined by two distinct points lying on it. The distance between lines is the smallest distance between a pair of points $(x, y)$ such that $x$ lies on the first line and $y$ lies on the second one.

The distance between the points $(x_1, \ldots, x_n)$ and $(y_1, \ldots, y_n)$ in $n$-dimensional space is defined as $$ \sqrt{\sum_{i=1}^n (x_i - y_i)^2}\text{.} $$

The $n$-dimensional line containing two points $a$ and $b$ could be formally defined as the set of points $(t a_1 + (1-t)b_1, t a_2 + (1-t)b_2, \ldots, t a_n + (1-t)b_n)$ for all real values of $t$.

The first line contains the integer $n$ ($1 \le n \le 100\,000$), the number of dimensions. The next four lines contain the description of four points $a$, $b$, $c$, $d$ in $n$-dimensional space. The points $a$ and $b$ lie on the first line, and the points $c$ and $d$ lie on the second one ($a \neq b$, $c \neq d$). Each of these four lines contains $n$ integers. All the numbers in the input do not exceed $10^5$ by absolute value.

Let $d$ be the distance between the lines. Print $d^2$ as a fraction $x$/$y$ such that $x \ge 0$, $y > 0$, and the greatest common divisor of $x$ and $y$ is equal to $1$.