ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2005 Round I

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Bill Clevers

Time limit: 1.0 second
Memory limit: 64 MB
System administrator with a well sounding name of Bill Clevers pays great attention to operating system security vulnerabilities. He truly believes that a system protection must be rather original to be reliable. So he decided to design a new public key cryptography system. No sooner said than done. One sleepless night, a little use of his favourite shamanic tambourine (did you hear about this important tool of system administrator?), a couple of broken computers, and a brand new cryptographic system is designed!
In this crypto-system, public key is a pair of numbers (k, p) where p must be a prime number and 0 ≤ kp−1. Private key is a pair of numbers (x, y), which satisfies the following relation:
x2 + y2 = k (mod p)
Of course, Bill does not think that his cryptographic system is better than RSA, but it is definitely much less known to potential hackers.
Everything could be just fine, if Bill had not (unfairly!) restricted access to some Internet sites, which were used by the remarkable programmer Bob Buggins to create his software masterpieces. Evidently, this unfair act of Bill must be circumvented somehow. To do it, Bob just needs to recover Bill's own private key from the corresponding public key. But Bill's cryptographic system appears strong enough! That long-awaited private key still can't be found by Bob…

Input

Input contains two integers: k and p. Number p is a prime number, 2 ≤ p ≤ 106; 0 ≤ kp−1.

Output

Output any pair of integers x and y (0 ≤ xp−1, 0 ≤ yp−1) such that x2 + y2 = k (mod p). If there is no such a pair, output "NO SOLUTION".

Sample

inputoutput
1 3
0 2
Problem Author: Den Raskovalov
Problem Source: IX Urals Programming Contest. Yekaterinburg, April 19-24, 2005
To submit the solution for this problem go to the Problem set: 1375. Bill Clevers