Under construction

Still being built. Things may change

Additive and multiplicative inverses

Interview

Time limit1sMemory limit128 MB

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

Medium4 of 10

Topics
Number theory, Math, Implementation
Solved
No attempts yet

Problem

Let ZNZ_N be the set of integers from 00 to N−1N-1. For a,b,c∈ZNa, b, c \in Z_N, bb is the additive inverse of aa if (a+b) mod N=0(a + b) \bmod N = 0, and cc is the multiplicative inverse of aa if (a×c) mod N=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 (2≤N≤10122 \le N \le 10^{12}) and AA (1≤A<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 N−1N-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) mod 26=0(11 + 15) \bmod 26 = 0, and the multiplicative inverse is 1919 because (11×19) mod 26=1(11 \times 19) \bmod 26 = 1.

Examples3

  1. Example 1

    Input
    26 11
    
    Expected output
    15 19
    
  2. Example 2

    Input
    100 20
    
    Expected output
    80 -1
    
  3. Example 3

    Input
    32760247633 22801763489
    
    Expected output
    9958484144 12390598440