수학 선생님의 고민(Hard)

이 문제는 수학 선생님의 고민(Easy)의 상위 문제이고, 수학 선생님의 고민(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

차형준 선생님은 여느 때처럼 재미있는 문제를 고민하다가, 양의 정수 $n$에 대한 이차식 $n x^2 + (n+1) x - (n+2)$를 정수 범위에서 인수분해 하는 문제를 만들게 되었다.

$n$이 작을 때는 손으로 쉽게 계산할 수 있었지만, $n$이 커질수록 문제가 버거워졌다.

선생님은 수학은 잘 못해도 시키는 대로 코딩은 하는 도훈이에게 문제를 맡겼다. 그런데 도훈이는 ChatGPT가 알려준 코드를 복사해 붙여넣기만 해왔을 뿐이라, 실제로는 "Hello World!" 정도만 출력할 줄 안다. 그래서 도훈이는 늘 하던 대로 ChatGPT에게 코드를 부탁했다.

하지만 답변을 받는 도중 인터넷이 끊겨버렸다.

ChatGPT에게 프로그램을 만들어달라고 하다가 인터넷이 끊긴 모습이다.

도훈이를 도와 $n x^2 + (n+1) x - (n+2)$를 정수 범위에서 인수분해 하는 프로그램을 작성하여라.

첫 번째 줄에 양의 정수 $n$이 주어진다.

주어진 $n$에 대해 이차식 $n x^2 + (n+1) x - (n+2)$가 정수 범위에서 인수분해가 불가능하면 -1을 출력한다. 인수분해가 가능하면 $(ax+b)(cx+d)=n x^2 + (n+1) x - (n+2)$를 만족하는 네 정수 $a$, $b$, $c$, $d$를 공백으로 구분하여 출력한다. 가능한 $(a,b,c,d)$ 쌍이 여러 가지라면 그중 아무것이나 출력한다.

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