Math Teacher's Worry (Hard)

This problem is a harder version of Math Teacher's Worry (Easy). You can solve this problem and submit its correct code to Math Teacher's Worry (Easy) to get accepted.

Teacher Hyeongjun Cha was thinking about an interesting problem as usual. He came up with a problem that asks to factor the quadratic $n x^2 + (n+1) x - (n+2)$ over the integers, for a positive integer $n$.

For small $n$, he could work it out by hand. As $n$ grew, the problem became hard.

So the teacher gave the problem to Dohun, who is not strong at math but writes code as instructed. However, Dohun has only copied and pasted code that ChatGPT gave him, and he can barely print "Hello World!". So he asked ChatGPT to write the code, as he usually does.

But the internet went down while he was waiting for the answer.

The image shows the moment the internet cut out while Dohun was asking ChatGPT to write a program.

Help Dohun write a program that factors $n x^2 + (n+1) x - (n+2)$ over the integers.

The first line contains a positive integer $n$.

If $n x^2 + (n+1) x - (n+2)$ cannot be factored over the integers, print -1. Otherwise, print four integers $a$, $b$, $c$, $d$ separated by spaces, which means $(ax+b)(cx+d)=n x^2 + (n+1) x - (n+2)$. If there are several valid $(a,b,c,d)$ tuples, print any one of them.

$1\le n\le 2\times 10^6$.