Operation Save the Raffle Prize! (Hard)

Apart from the input constraints, there is no difference between the difficulty levels of this problem.

Every year APC gives out raffle prizes to participants on campus. This year's raffle will be drawn with a random number generator that Junpyo wrote himself, to keep the draw fair. A random number generator is a device that produces a sequence of numbers or symbols so that they cannot be predicted any further in theory.

Juheon: How do you know the generator your brother wrote is fair?

Junpyo: Don't worry! I'll implement the linear congruential method, which is used as an ANSI standard in C ~

Juheon: What's the linear congruential method?

Junpyo: Well, it goes like this..

Junpyo's explanation, summarized briefly:

X1 = (a × Seed + c) % m

X2 = (a × X1 + c) % m

...

Xn + 1 = (a × Xn + c) % m

In other words, random numbers are generated by the formula above from a, c, m, which Junpyo chooses in secret, and the Seed value, which the participants choose.

Juheon: Hmm... shouldn't a, c, m be chosen carefully?

Junpyo: Yeah. According to the Hull-Dobell theorem, you're right. But I'm too lazy, so I'll just make m some prime I like.

Juheon: (A prime my brother likes..? Heh..)

Juheon actually had an ambition to win a raffle prize this year no matter what! The conversation above was the groundwork for it! Juheon knew Junpyo so well that he already knew the prime Junpyo liked, and Junpyo was scheduled to demonstrate in front of everyone, before the real draw, that the generator works properly, in order to show the participants that the generator he wrote has no problems.

Juheon devised a scheme. During the demonstration, he will use the Seed chosen by the participants and the X1, X2 produced from it to find the a, c that Junpyo chose in secret. If Juheon does not win a raffle prize, he plans to expose the a, c he found and claim that everything was rigged, making the draw itself void! Juheon wants to write a program that finds a, c automatically.

One line gives the prime m that Junpyo likes, the Seed chosen by the participants, and the X1, X2 revealed by the demonstration. The input is always a feasible situation.

Print the integers a, c that Junpyo selected in secret. If there are multiple possible answers, print any one of them.

m ≤ 1000,000,000 (m is prime)

0 < Seed, X1, X2 < m

0 ≤ a, c < m

The rand() function in C is similar to the above, but it is implemented to return the top 16 bits of Xn.