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 ≤ k ≤ p−1. Private key is a pair of numbers (x, y), which satisfies the following relation:
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 contains two integers: k and p. Number p is a prime number, 2 ≤ p ≤ 106; 0 ≤ k ≤ p−1.
Output any pair of integers x and y (0 ≤ x ≤ p−1, 0 ≤ y ≤ p−1) such that x2 + y2 = k (mod p). If there is no such a pair, output "NO SOLUTION".
Problem Author: Den Raskovalov
Problem Source: IX Urals Programming Contest. Yekaterinburg, April 19-24, 2005