ALMISPY  Almostisosceles Pythagorean triple (easy)
(3, 4, 5) is the smallest almostisosceles Pythagorean triple,
as 4  3 = 1.
Let S = { (a, a+1, c)  a^{2} + (a+1)^{2} = c^{2} with a and c positive integers}.
One can prove that the set S of almostisosceles Pythagorean triples is infinite.
There is an obvious total order on this set.
Input
The first line of input contains an integer
T, the number of test cases.
On each of the next T lines, your are given
two integers n and m.
Output
For each test case, you have to find the nth triple (a, a+1, c) in the ordered set S, and print a and c. As the answer could not fit in a 64bit container, simply output your answer modulo m.
Example
Input: 3 1 10 2 123 4 289
Output: 3 5 20 29 118 118
Constraints
0 < T < 10^4 0 < n < 10^18 1 < m < 10^9
For your information, my 500Bpython3 code get AC in 1.61s with 12MB of memory print.
In Python2.7 : (2.49s, 4.0MB), in Python2+psyco (2.04s, 36MB).
My 1kB C code ran in (0.04s, 1.6MB), and time limit is ×125 this one.
Have fun ;)
(edit) With wisfaq observation, all my best timings are divided by exactly two!!!
(Edit 20170211, new TL with new compiler. TL 1.11s, in the third (0.37s) my Python3 code ends.)
hide comments
[Lakshman]:
20130724 15:23:48
Please help What is the answer for


[Lakshman]:
20130718 19:10:13
@francky Can you please tell me why getting WA, I think my approach is correct.


Orchid:
20130624 05:57:45
9539091 any hint??checked smaller moduli also.. 

SWOOSH!!!:
20130624 05:56:15
Will a always be less than c for any mod?


tuhin:
20130624 04:45:30
AC :) Last edit: 20130704 04:33:34 

Abhishek Agrawal:
20130607 07:34:53
why i am getting RTE while i am getting right output


Ouditchya Sinha:
20130606 12:22:23
@Franky, I can't seem to optimise my code below 0.24s, any tips?


Shashi Kant Prasad:
20130511 16:46:59
Is it correct:


Shashi Kant Prasad:
20130511 15:42:54
Hi Francky, getting WA. Plz, tell me where my soln is failing. My last submission: 9242428


Mukund Kumar:
20130511 08:03:54
@Author:I am getting segsegv...finding a and c with 2*2 matrix..What should i do?any suggestion is welcomed..

Added by:  Francky 
Date:  20130430 
Time limit:  1.110s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 