#include using namespace std; #define modulo 1000000007 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 10000000 int main(){ int N; cin>>N; vector V; for(int i=0;true;i++){ if(i*i>N)break; V.push_back(i*i); } int mini = Inf; vector ans; for(int i=1;imini)continue; if(V[i]==N){ vector A; A.push_back(i); ans = A; } for(int j=1;jmini||ans.size()==1)continue; if(V[i]+V[j]==N){ vector A={i,j}; sort(A.begin(),A.end(),greater()); if(A>ans||mini>i+j){ ans = A; mini=i+j; } } for(int k=1;kmini||ans.size()==2)continue; if(V[i]+V[j]+V[k]==N){ vector A={i,j,k}; sort(A.begin(),A.end(),greater()); if(A>ans||mini>i+j+k){ ans=A; mini=i+j+k; } } if(ans.size()==3)continue; int ind = lower_bound(V.begin(),V.end(),N-V[i]-V[j]-V[k])-V.begin(); if(ind==N)continue; if(V[i]+V[j]+V[k]+V[ind]==N){ vector A = {i,j,k,ind}; sort(A.begin(),A.end(),greater()); if(A>ans||mini>i+j+k+ind){ ans=A; mini=i+j+k+ind; } } } } } int last = 0; if(ans[0]!=ans[ans.size()-1]){ while(true){ if(ans[ans.size()-1]!=1)break; vector A; A.push_back(1); for(int i=0;i