s=sorted
while input():
r=(0,1),
for p,e in eval(input()):a=p%4<3;b=p-1|1;r*=a|~e%2;exec(a*'while~a**2%p:e+=1;a=pow(e,p//4,p)\nwhile b*b>p:a,b=b%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).