var i,j,ans,d:longint;

     t,r,m:int64;

 function flag(x,y:longint):longint;

 var t:longint;

 begin

   if (x<y) then

   begin

     t:=x;

     x:=y;

     y:=t;

   end;

   x:=x mod y;

   if (x=) then exit(y) else exit(flag(x,y));

 end;

 begin

   readln(r);

   ans:=;

   t:=*r;

   for d:= to trunc(sqrt(t)) do

     if (t mod d=) then

     begin

       for i:= to trunc(sqrt(r/d)) do

       begin

         j:=trunc(sqrt(t/d-i*i));

         if (j=sqrt(t/d-i*i)) and (i<>j) and (flag(i,j)=) then inc(ans);

       end;

       for i:= to trunc(sqrt(d/)) do

       begin

         j:=trunc(sqrt(d-i*i));

         if (j*j=d-i*i) and (i<>j) and (flag(i,j)=) then inc(ans);

       end;

     end;

   ans:=ans*+;

   writeln(ans);

 end.

 var i,j,k,l,tot,g:longint;

     c,s:array[..] of longint;

     f:array[..] of int64;

     ans:int64;

 function f1(x:longint):int64;

 begin

   if (x>=) then exit(f[x]) else exit();

 end;

 begin

   fillchar(c,sizeof(c),);

   fillchar(f,sizeof(f),);

   readln(c[],c[],c[],c[],tot);

   f[]:=;

   for i:= to  do

     for j:=c[i] to  do

       f[j]:=f[j]+f[j-c[i]];

   for i:= to tot do

   begin

     fillchar(s,sizeof(s),);

     for j:= to  do

       read(s[j]);

     readln(g);

     ans:=f[g];

     for j:= to  do

       ans:=ans-f1(g-(s[j]+)*c[j]);

     for j:= to  do

       for k:=j+ to  do

         if (j<>k) then

           ans:=ans+f1(g-(s[j]+)*c[j]-(s[k]+)*c[k]);

     for j:= to  do

       for k:=j+ to  do

         for l:=k+ to  do

           if (j<>k) and (k<>l) and (j<>l) then

             ans:=ans-f1(g-(s[j]+)*c[j]-(s[k]+)*c[k]-(s[l]+)*c[l]);

     ans:=ans+f1(g-(s[]+)*c[]-(s[]+)*c[]-(s[]+)*c[]-(s[]+)*c[]);

     writeln(ans);

   end;

 end.

 var n,m,i,j,k,ans,left,right,max,anss,s,now1,x,y:longint;

     l,sl,ty:array[..] of longint;

     f,f1:array[..,-..] of longint;

 function tryit(x:longint):boolean;

 var i,j,s,left,right:longint;

 begin

   i:=;

   j:=;

   now1:=;

   while (i<n) do

   begin

     left:=i+;

     right:=n;

     i:=(left+right) div ;

     while (right-left>) do

     begin

       if (sl[i]-sl[now1]<=x) then left:=i else right:=i;

       i:=(left+right) div ;

     end;

     if (sl[right]-sl[now1]<=x) then i:=right else i:=left;

     if (sl[n]-sl[now1]>x) then inc(j);

     now1:=i;

   end;

   if (j>m) then exit(false) else exit(true);

 end;

 begin

   read(n,m);

   fillchar(l,sizeof(l),);

   fillchar(sl,sizeof(sl),);

   s:=;

   max:=;

   for i:= to n do

   begin

     read(l[i]);

     sl[i]:=sl[i-]+l[i];

     if (l[i]>max) then max:=l[i];

     s:=s+l[i];

   end;

   left:=max;

   right:=s;

   ans:=(left+right) div ;

   while (right-left>) do

   begin

     if not(tryit(ans)) then left:=ans else right:=ans;

     ans:=(left+right) div ;

   end;

   ans:=right;

   if tryit(left) then ans:=left;

   write(ans,' ');

   fillchar(f,sizeof(f),);

   fillchar(ty,sizeof(ty),);

   fillchar(f1,sizeof(f1),);

   anss:=;

   f[,]:=;

   for i:= to n do

     f1[,i]:=;

   k:=;

   for j:= to n do

   begin

     while (sl[j]-sl[k]>ans) do inc(k);

     ty[j]:=k;

   end;

   for i:= to m+ do

   begin

     x:=i mod ;

     y:=-x;

     for j:= to n do

     begin

       f[y,j]:=(f1[x,j-]-f1[x,ty[j]-]+) mod ;

       f1[y,j]:=(f[y,j]+f1[y,j-]) mod ;

     end;

     anss:=(anss+f[y,n]) mod ;

   end;

   writeln(anss);

 end.

 var n,i,j:longint;

     sum,ave,ans:int64;

     a,p:array[..] of longint;

 procedure qsort(lx,rx:longint);

 var i,j,m,x:longint;

 begin

   i:=lx;

   j:=rx;

   m:=p[(i+j) div ];

   repeat

     while (p[i]<m) do inc(i);

     while (p[j]>m) do dec(j);

     if (i<=j) then

     begin

       x:=p[i];

       p[i]:=p[j];

       p[j]:=x;

       inc(i);

       dec(j);

     end;

   until (i>j);

   if (i<rx) then qsort(i,rx);

   if (j>lx) then qsort(lx,j);

 end;

 begin

   readln(n);

   fillchar(a,sizeof(a),);

   fillchar(p,sizeof(p),);

   sum:=;

   for i:= to n do

   begin

     readln(a[i]);

     sum:=sum+a[i];

   end;

   ave:=sum div n;

   for i:= to n do

     p[i]:=p[i-]-ave+a[i];

   qsort(,n);

   ans:=;

   for i:= to n do

     ans:=ans+abs(p[i]-p[n div +]);

   writeln(ans);

 end.

 type arr=array[..,..] of longint;

 const modp=;

     tx:array[..] of longint=(,-,,);

     ty:array[..] of longint=(,,,-);

 var i,j,k,s,t,s1,s2,rx,ry,swap,rh:longint;

     q:array[..*] of arr;

     mark:array[..*] of boolean;

     step:array[..*] of longint;

     ans:arr;

     ch:char;

 function hash(x:arr):longint;

 var i,j,ans,now:longint;

 begin

   ans:=;

   now:=;

   for i:= to  do

     for j:= to  do

     begin

       ans:=(ans+int64(now*x[i,j]));

       now:=(now+now);

     end;

   exit(ans);

 end;

 begin

   s:=;

   t:=;

   fillchar(q,sizeof(q),);

   fillchar(ans,sizeof(ans),);

   for i:= to  do

   begin

     for j:= to  do

     begin

       read(ch);

       while (ch<>'') and (ch<>'') do read(ch);

       q[,i,j]:=ord(ch)-;

     end;

   end;

   for i:= to  do

   begin

     for j:= to  do

     begin

         read(ch);

         while (ch<>'') and (ch<>'') do read(ch);

         ans[i,j]:=ord(ch)-;

     end;

   end;

   s1:=hash(q[s]);s2:=hash(ans);

   mark[s1]:=true;

   fillchar(step,sizeof(step),);

   if (s1=s2) then writeln('') else

   begin

     while (s<t) do

     begin

       for i:= to  do

         for j:= to  do

           if (q[s,i,j]>) then

           begin

             for k:= to  do

             begin

               rx:=i+tx[k];ry:=j+ty[k];

               if  (<=rx) and (rx<=) and (<=ry) and (ry<=) and (q[s,rx,ry]=) then

               begin

                 swap:=q[s,i,j];q[s,i,j]:=q[s,rx,ry];q[s,rx,ry]:=swap;

                 rh:=hash(q[s]);

               if not(mark[rh]) then

                 begin

                   if (rh=s2) then

                   begin

                     writeln(step[s]+);

                     halt;

                   end;

                   mark[rh]:=true;

                   q[t]:=q[s];

                   step[t]:=step[s]+;

                   inc(t);

                 end;

                 swap:=q[s,i,j];q[s,i,j]:=q[s,rx,ry];q[s,rx,ry]:=swap;

               end;

               end;

             end;

         inc(s);

         end;

     end;

 end.

 const ch:array[..] of char=('W','I','N','G');

 var i,j:longint;

     f,flag:array[..,..,..] of boolean;

     x:array[..,..,..] of char;

     a:array[..] of longint;

     s:string;

     flagg:boolean;

 function calc(x:char):longint;

 begin

   if (x='W') then exit()

   else if (x='I') then exit()

   else if (x='N') then exit()

   else if (x='G') then exit();

 end;

 function f1(k,left,right:longint):boolean;

 var i,j,t1,t2:longint;

 begin

   if flag[k,left,right] then exit(f[k,left,right]);

   flag[k,left,right]:=true;

   if (right=left) and (s[left]=ch[k]) then

   begin

     f[k,left,right]:=true;

     exit(true);

   end;

   for i:= to a[k] do

   begin

     t1:=calc(x[k,i,]);

     t2:=calc(x[k,i,]);

     for j:=left to right- do

       if f1(t1,left,j) and f1(t2,j+,right) then

       begin

         f[k,left,right]:=true;

         exit(true);

       end;

   end;

   f[k,left,right]:=false;

   exit(false);

 end;

 begin

   fillchar(a,sizeof(a),);

   for i:= to  do

     read(a[i]);

   readln;

   fillchar(f,sizeof(f),false);

   fillchar(flag,sizeof(flag),false);

   for j:= to  do

     for i:= to a[j] do

       readln(x[j,i,],x[j,i,]);

   readln(s);

   flagg:=false;

   for i:= to  do

     if f1(i,,length(s)) then

     begin

       write(ch[i]);

       flagg:=true;

     end;

   if not(flagg) then write('The name is wrong!');

   writeln;

 end.