typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
const LL INF=0x3f3f3f3f3f3f3f3f;
inline LL sqr(LL x){ return x*x; }
inline LL dis(const VI &a,const VI &b) {
    return sqr(a[0]-b[0])+sqr(a[1]-b[1]);
}
bool cmp(const VI &a, const VI &b) {
    return a[1]<b[1];
}
VVI tmp;
LL help(VVI &ps,int l,int r) {
    int n=r-l+1;
    if(n<=3) {
        LL ans=INF;
        for(int i=l;i<=r;i++) {
            for(int j=i+1;j<=r;j++)
                ans=min(ans,dis(ps[i],ps[j]));
        }
        sort(ps.begin()+l, ps.begin()+r+1, cmp);
        return ans;
    }
    int m=(l+r)>>1;
    int mp=ps[m][0];
    LL ans=min(help(ps,l,m),help(ps,m+1,r));
    int i=l,j=m+1,p=l;
    while(i<=m || j<=r) {
        if(i>m || j<=r&&cmp(ps[j],ps[i])) {
            tmp[p++]=ps[j++];
        } else {
            tmp[p++]=ps[i++];
        }
    }
    copy(tmp.begin()+l, tmp.begin()+r+1,ps.begin()+l);
    p=0;
    for(int i=l;i<=r;i++) {
        if(sqr(ps[i][0]-mp) >= ans) continue;
        for(int j=p-1;j>=0 && sqr(ps[i][1]-tmp[j][1]) < ans;j--) {
            ans=min(ans,dis(ps[i],tmp[j]));
        }
        tmp[p++]=ps[i];
    }
    return ans;
}
int solve(vector<vector<int>>& ps) {
    tmp=ps;
    sort(ps.begin(),ps.end());
    return help(ps,0,ps.size()-1);
}