Additive and multiplicative inverses

Given N and A, print the additive inverse of A modulo N and the multiplicative inverse if it exists, otherwise -1.

Medium4Number theoryMathImplementationInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

Let ZNZ_N be the set of integers from 00 to N1N-1. For a,b,cZNa, b, c \in Z_N, bb is the additive inverse of aa if (a+b)modN=0(a + b) \bmod N = 0, and cc is the multiplicative inverse of aa if (a×c)modN=1(a \times c) \bmod N = 1.

You are given integers NN and AA. Find the additive inverse and the multiplicative inverse of AA in ZNZ_N. If the multiplicative inverse does not exist, print 1-1 for it.

Input

The first line contains NN (2N10122 \le N \le 10^{12}) and AA (1A<N1 \le A < N), separated by a space.

Output

Print the additive inverse and the multiplicative inverse of AA in ZNZ_N on one line, separated by a space. If the multiplicative inverse does not exist, print 1-1 in its place.

Both inverses are integers in the range 00 to N1N-1, and each of them is unique when it exists.

Hint

For N=26N = 26 and A=11A = 11, the additive inverse is 1515 because (11+15)mod26=0(11 + 15) \bmod 26 = 0, and the multiplicative inverse is 1919 because (11×19)mod26=1(11 \times 19) \bmod 26 = 1.