#include <fstream>
#define pinf 1000000007
#define f first
#define s second
using namespace std;

ifstream fin ("bibel.in");
ofstream fout ("bibel.out");

int z, n, d[132000][25], niv, aux, p, ant, dist[210][210], mini, nr, inc, rez[25], nbant, incant, p2;
pair <int, int> b[210];

void rez_niv()
{
    int i, j, r;

    n=nr-inc+1;

    for (i=0; i<nr; i++)
    {
        for (j=i+1; j<=nr; j++)
        {
            dist[i][j]=dist[j][i]=(b[j].f-b[i].f)*(b[j].f-b[i].f)+(b[j].s-b[i].s)*(b[j].s-b[i].s);
        }
    }

    aux=((1<<n)-1);

    for (i=1; i<=aux; i++)
    {
        for (j=0; j<n; j++)
            d[i][j]=pinf;
    }

    for (i=1; i<=aux; i++)
    {
        for (j=0; j<n; j++)
        {
            p=1<<j;

            if ((p&i)>0)
            {
                ant=i-p;
                    if (ant==0)
                    {
                        for (r=0; r<nbant; r++)
                        {
                            if (rez[r]+dist[r+incant][j+inc]<d[i][j])
                            {
                                d[i][j]=rez[r]+dist[r+incant][j+inc];
                            }
                        }
                    }
                    else
                    for (r=0; r<n; r++)
                    {
                        if (d[ant][r]+dist[r+inc][j+inc]<d[i][j])
                        {
                            d[i][j]=d[ant][r]+dist[r+inc][j+inc];
                        }
                    }
            }
        }
    }

    mini=pinf;

    for (i=0; i<n; i++)
    {
            if (d[aux][i]<mini)
                mini=d[aux][i];

            rez[i]=d[aux][i];

    }

    fout<<mini<<'\n';

    nbant=n;
    incant=inc;
}

int main()
{
    n=0;
    niv=0;
    inc=0;
    nbant=1;

    while (fin>>z)
    {
        if (z==0)
        {
            nr++;
            fin>>b[nr].f>>b[nr].s;
        }
        else
        {
            if (z==1)
            {
                niv++;
                rez_niv();
                inc=nr+1;
            }
        }
    }

    fin.close();
    fout.close();
    return 0;
}