s=sorted
while input():
r=(0,1),
for p,e in input():a=p%4<3;b=p-1|1;r*=a|~e%2;exec'while~a**2%p:e+=1;a=pow(e,p/4,p)\nwhile b*b>p:a,b=b%a,a'*a+e/(2-a)*'\nr=s({tuple(s([abs(b*c-A*d),b*d+A*c]))for A in(-a,a)for c,d in r})'
print' = '.join('%d^2 + %d^2'%x for x in r)
Note that non-ascii characters in the above source code will be escaped (such as \x9f).