Inverse Inverse Problem

Here's a simple problem :

"Given integers A, B, X, N and a prime P, let f(x) = Ax + B and define fⁿ(x) as f(f(...f(x)...)), where the function f is iterated n times. Calculate the value of f^N(X) modulo P."

This is a classic problem, but have you ever tried the inverse problem?

"Given x, n, t, p, where 0 ≤ t < p ≤ n and p is a prime. Find nonnegative integers a, b where 1 ≤ a ≤ p - 1, 0 ≤ b ≤ p - 1 such that the answer to the testcase (A, B, X, N, P) = (a, b, x, n, p) is t, or determine if it's impossible."

This is still too easy, so now let's try to solve the inverse of the inverse problem.

For a testcase x, n, t, p to the inverse problem, define g(x, n, t, p) as -1 if there is no solution for a, b and the smallest possible value of a in a valid solution to this testcase otherwise. For example, g(1, 2, 31, 101) = 1 as a = 1, b = 15 is a valid solution.

Given an integer M, find a testcase x, n, t, p such that p ≤ M and the value of g(x, n, t, p) is maximal.

The input contains a single integer, M (3 ≤ M ≤ 105).

The output should contain 4 space-separated integers, x, n, t, p, denoting your testcase. The testcase must satisfy the constraints 1 ≤ x ≤ 109, 1 ≤ n ≤ 1018, 0 ≤ t < p ≤ M and p is prime.

Your testcase will be accepted if it satisfies all constraints and g(x, n, t, p) is maximum possible under the current constraints. If there are multiple solutions, you may output any of them.

8

2018 231 1 7

You can check that g(2018, 231, 1, 7) = 3. (For instance, a = 3, b = 4 is a solution and there are no solutions for a ≤ 2)