Description

Define the difference measure between integers $p,q,r,s$ and the given integers $a,b,c,d$ as

$$M=\Big|\left(a^2+b^2\right)\left(p^2+q^2\right)+\left(c^2+d^2\right)\left(r^2+s^2\right)+2\big(ac+bd\big)\big(pr-qs\big)+2\big(bc-ad\big)\big(ps+qr\big)\Big|$$

Your task is to find the smallest non-zero value of the difference measure $M$, and one set of $p,q,r,s$ that achieves this smallest non-zero value. It is guaranteed that the smallest non-zero value of $M$ exists and is less than $2^{63}$. It is also guaranteed that there exists a set of $p,q,r,s$ with all absolute values less than $2^{63}$ such that $M$ attains the smallest non-zero value.

Input Format

Input one line with four integers $a,b,c,d$, as described above.

Output Format

Output one line with five integers $p,q,r,s,M$, representing a set of $p,q,r,s$ that makes the difference measure $M$ reach its smallest non-zero value, and the value of $M$ at that time.

1 9 2 6

2 1 -3 1 2

19674937 18722417 163948077 124500851

146134 -61558 -18260 -10209 221162

Hint

Sample Explanation #1

Obviously, when $a=1,b=9,c=2,d=6$, the difference measure $M$ must be even, so $M$ cannot take any non-zero value smaller than $2$.

Constraints

Test Point ID	Special Property
$1$	$c=d=0$
$2$	$a=c=0$
$3$	$b=d=0$
$4$	$ad=bc$
$5$	$\vert a\vert,\vert b\vert,\vert c\vert,\vert d\vert\le10$
$6\sim10$	None

For $100\%$ of the testdata, $\vert a\vert,\vert b\vert,\vert c\vert,\vert d\vert\le10^9$.

Scoring Method

You must ensure that the number of values you output for each test point is $5$ and that $\vert p\vert,\vert q\vert,\vert r\vert,\vert s\vert,\vert M\vert<2^{63}$, to avoid unexpected errors.

For each test point, if your $M$ is the same as the standard output, you will get $4$ points. If the $p,q,r,s$ you output can make the computed result equal to $M$, you will get another $6$ points.

Translated by ChatGPT 5