#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define st first
#define nd second

using namespace std;

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

const int Dim = 1 << 17;
const int INF = 0x3f3f3f3f;

typedef pair< int,int > Point;

int Path[Dim][17],N[2],T[18],Sol;
Point B[2][18];

inline int Dst(Point A,Point B)
{
    return (A.st - B.st) * (A.st - B.st) + (A.nd - B.nd) * (A.nd - B.nd);
}

inline int Min(int A,int B)
{
    return (A < B) ? A : B;
}

inline int Count(int i)
{
    int Nr = 0;
    while(i)
        Nr++,i &= i - 1;

    return Nr;
}

int main()
{
    int Op,lvl = 0;

    N[1] = 1;

    do
    {
        do
        {
            fin >> Op;
            if (Op == 0)
            {
                N[lvl]++;
                fin >> B[lvl][N[lvl]].st >> B[lvl][N[lvl]].nd;
            }
        }while(Op == 0);

        if (Op == 1)
        {
            for (int i = 1;i <= N[lvl];i++)
            {
                Path[1 << (i - 1)][i] = INF;
                for (int j = 1;j <= N[lvl ^ 1];j++)
                    Path[1 << (i - 1)][i] = Min(Path[1 << (i - 1)][i],T[j] + Dst(B[lvl][i],B[lvl ^ 1][j]));
            }

            for (int i = 1;i < (1 << N[lvl]);i++)
               if (Count(i) > 1)
                for (int j = 1;j <= N[lvl];j++)
                {
                    Path[i][j] = INF;
                    if (i & (1 << (j - 1)))
                     for (int k = 1;k <= N[lvl];k++)
                      if (i & (1 << (k - 1)) && j != k)
                       Path[i][j] = Min(Path[i][j],Path[i ^ (1 << (j - 1))][k] + Dst(B[lvl][j],B[lvl][k]));
                }

            Sol = INF;

            for (int i = 1;i <= N[lvl];i++)
                Sol = Min(Sol,Path[(1 << N[lvl]) - 1][i]),
                T[i] = Path[(1 << N[lvl]) - 1][i];

            lvl ^= 1;
            N[lvl] = 0;
            memset(Path,0,sizeof(Path));

            fout << Sol << "\n";
        }
    }while(Op != 2);
    return 0;
}