25399번 - 라그랑주님 수학에는 뺄셈도 있어요 스페셜 저지

라그랑주의 네 제곱수 정리란, 어떤 자연수 N을 최대 4개의 제곱수들의 합으로 나타낼 수 있다는 정리이다. 예를 들면, 30 = 1² + 2² + 3² + 4²으로 나타낼 수 있고, 1217 = 34² + 6² + 5²으로 나타낼 수 있다.

하지만 BOJ에서 문제를 푸는 사람들은 수학을 열심히 공부했기 때문에, 덧셈 뿐만 아니라 뺄셈도 할 줄 안다. 하이비는 이러한 사람들을 위해 위 정리의 업그레이드 버전인 다음 추측을 만들었다.

"정수 N은 1개 이상 M개 이하의 서로 다른 양의 제곱수들을 더하고 빼서 만들 수 있다."

예를 들면, 30 = 5² + 3² - 2²으로, 8 = 3² - 1²으로, -16 = -4²으로 나타낼 수 있다.

하이비는 위와 같은 추측을 만들었지만, 위 추측을 만족시키는 M을 찾지 못했다. 그래서 당신에게 N이 주어질 때, N을 만들기 위해 필요한 양의 제곱수의 최소 개수를 찾아주는 프로그램을 만들어달라고 부탁해왔다.

하이비를 위해 정수 N을 만들기 위한 양의 제곱수의 최소 개수를 찾는 프로그램을 대신 짜주자.

첫째 줄에 만들어야 할 정수 N이 주어진다.

만약 N을 만들 수 없으면 첫째 줄에 -1을 출력한다.

그렇지 않다면, 첫째 줄에 사용한 양의 제곱수의 개수 K을 출력한 뒤, K개의 줄에 걸쳐서 다음 형식으로 N을 만드는 방식을 출력한다.

• + X: X²을 더한다.
• - X: X²을 뺀다.

• |N| ≤ 10¹²
• 1 ≤ K
• 1 ≤ X ≤ 10¹²
• 출력하는 모든 X는 달라야 한다.