using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
using System.Text;
using static Constants;
using static Common;

public static class Common
{
    public static void Swap<T>(ref T lhs, ref T rhs)
    {
        T temp = lhs;
        lhs = rhs;
        rhs = temp;
    }
}

public static class Constants
{
    public const int N = 100;
    public const int M = 8;

    public const int UniverseSize = 1000;
    public const int Alpha = 5;

    public const int TypePlanet = 1;
    public const int TypeStation = 2;
}

public struct PointD
{
    public double X;
    public double Y;


    public PointD(Point p)
    {
        X = p.X;
        Y = p.Y;
    }

    public PointD(int x, int y)
    {
        X = x;
        Y = y;
    }

    public PointD(double x, double y)
    {
        X = x;
        Y = y;
    }

    public static bool operator ==(PointD a, PointD b)
    {
        if ((object)a == null || (object)b == null)
        {
            if ((object)a == null && (object)b == null)
            {
                return true;
            }
            return false;
        }

        return (a.X == b.X && a.Y == b.Y);
    }

    public static bool operator !=(PointD a, PointD b)
    {
        if ((object)a == null || (object)b == null)
        {
            if ((object)a == null && (object)b == null)
            {
                return false;
            }
            return true;
        }

        return (a.X != b.X || a.Y != b.Y);
    }

    public static PointD operator *(PointD a, double i)
    {
        return new PointD(a.X * i, a.Y * i);
    }

    public static PointD operator /(PointD a, double i)
    {
        return new PointD(a.X / i, a.Y / i);
    }

    //objと自分自身が等価のときはtrueを返す
    public override bool Equals(object obj)
    {
        if (obj == null || GetType() != obj.GetType())
        {
            return false;
        }

        PointD p = (PointD)obj;
        return (X == p.X && Y == p.Y);
    }

    //Equalsがtrueを返すときに同じ値を返す
    public override int GetHashCode()
    {
        int prime = 31;
        int result = 1;
        long temp;
        temp = BitConverter.DoubleToInt64Bits(X);
        result = prime * result + (int)(temp ^ (temp >> 32));
        temp = BitConverter.DoubleToInt64Bits(Y);
        result = prime * result + (int)(temp ^ (temp >> 32));
        return result;
    }

    public static PointD operator +(PointD a, PointD b)
    {
        return new PointD(a.X + b.X, a.Y + b.Y);
    }

    public static PointD operator -(PointD a, PointD b)
    {
        return new PointD(a.X - b.X, a.Y - b.Y);
    }

    public static PointD operator +(PointD a)
    {
        return new PointD(+a.X, +a.Y);
    }

    public static PointD operator -(PointD a)
    {
        return new PointD(-a.X, -a.Y);
    }

    public override string ToString()
    {
        return $"({X},{Y})";
    }

    public double Distance2(Point p)
    {
        return (p.X - X) * (p.X - X) + (p.Y - Y) * (p.Y - Y);
    }

    public Point Round()
    {
        return new Point((int)X, (int)Y);
    }
}


public static class ExMethods
{
    public static PointD Average2(this IEnumerable<Point> points)
    {
        var n = points.Count();
        if (n == 0)
        {
            return new PointD(-1, -1);
        }

        var sum2 = points.Select(p => new Point(p.X*p.X, p.Y*p.Y)).Aggregate((a, b) => a + b);
        var p = new PointD(sum2) / points.Count();
        return new PointD(Math.Sqrt(p.X), Math.Sqrt(p.Y));
    }
}

namespace Edmonds
{
    public enum TreeLevel
    {
        EVEN,
        ODD,
        DUMBBELL
    }

    public class Blossom
    {
        public Blossom()
        {
            charge = 0;
            treeLevel = TreeLevel.EVEN;
            treeParentBlossom = null;
            treeParentEdge = null;
            outwardBlossom = null;
        }

        public double Charge => charge;
        public TreeLevel TreeLevel => treeLevel;

        public void AddCharge(double delta)
        {
            charge += delta;
            UpdateVertexTotal(delta);
        }

        public void UpdateCharge(double reserve)
        {
            if (TreeLevel == TreeLevel.EVEN)
            {
                AddCharge(reserve);
            }
            else
            {
                AddCharge(-reserve);
            }
            foreach (var child in treeChildren)
            {
                child.UpdateCharge(reserve);
            }
        }

        public Blossom GetOutermostBlossom()
        {
            Blossom outermost = this;
            while (outermost.outwardBlossom != null)
            {
                outermost = outermost.outwardBlossom;
            }
            return outermost;
        }

        public Blossom GetInnerBlossomContaining(Vertex v)
        {
            Blossom inner = v;
            while (inner != null && inner.outwardBlossom != this)
            {
                inner = inner.outwardBlossom;
            }
            return inner;
        }

        public Blossom GetRootBlossom()
        {
            Blossom root = this;
            while (root.treeParentBlossom != null)
            {
                root = root.treeParentBlossom;
            }
            return root;
        }

        public virtual Vertex GetStem()
        {
            return innerChildren[0].GetStem();
        }

        public void FlipPathAndDisassemble(Vertex v, Blossom pair = null, Edge pairEdge = null)
        {
            Vertex v2 = GetStem();
            if (TreeLevel == TreeLevel.ODD)
            {
                v2 = treeParentEdge.V1;
                if (v2.GetOutermostBlossom() != this)
                {
                    v2 = treeParentEdge.V2;
                }
            }
            FlipPathBetween(v, v2);
            if (TreeLevel == TreeLevel.EVEN)
            {
                foreach (var child in treeChildren)
                {
                    if (child != pair)
                    {
                        child.DisassembleTreeIntoDumbbells();
                    }
                }
            }
            treeChildren.Clear();
            Blossom parent = treeParentBlossom;
            Edge parentEdge = treeParentEdge;
            treeParentBlossom = null;
            treeParentEdge = null;
            TreeLevel oldTreeLevel = TreeLevel;
            if (pair != null)
            {
                MakeDumbbellWith(pair, pairEdge);
            }
            if (parent == null)
            {
                return;
            }
            Vertex pv = parentEdge.V1;
            if (pv.GetOutermostBlossom() == this)
            {
                pv = parentEdge.V2;
            }
            parentEdge.Flip();
            if (oldTreeLevel == TreeLevel.EVEN)
            {
                parent.FlipPathAndDisassemble(pv);
            }
            else
            {
                parent.FlipPathAndDisassemble(pv, this, parentEdge);
            }
        }

        public void DisassembleTreeIntoDumbbells()
        {
            if (TreeLevel == TreeLevel.EVEN)
            {
                foreach (var child in treeChildren)
                {
                    child.DisassembleTreeIntoDumbbells();
                }
                treeChildren.Clear();
                treeParentBlossom = null;
                treeParentEdge = null;
            }
            else
            {
                Blossom pair = treeChildren.First.Value;
                Edge pairEdge = treeChildren.First.Value.treeParentEdge;
                pair.DisassembleTreeIntoDumbbells();
                treeChildren.Clear();
                treeParentBlossom = null;
                treeParentEdge = null;
                MakeDumbbellWith(pair, pairEdge);
            }
        }

        public void FlipPathBetween(Vertex v1, Vertex v2)
        {
            if (GetStem() != v1)
            {
                Swap(ref v1, ref v2);
            }
            if (innerChildren.Count == 0)
            {
                return;
            }
            Blossom b2 = GetInnerBlossomContaining(v2);
            Blossom first = innerChildren[0];
            Blossom last = b2;
            int pos = innerChildren.FindIndex(c => c == b2);
            if (pos % 2 == 1)
            {
                Swap(ref v1, ref v2);
                Swap(ref first, ref last);
            }
            Blossom current = first;
            while (current != last)
            {
                Vertex b_v1 = current.nextBlossomEdge.V1;
                Vertex b_v2 = current.nextBlossomEdge.V2;
                if (GetInnerBlossomContaining(b_v1) != current)
                {
                    Swap(ref b_v1, ref b_v2);
                }
                current.FlipPathBetween(v1, b_v1);
                current.nextBlossomEdge.Flip();
                current = GetInnerBlossomContaining(b_v2);
                v1 = b_v2;
            }
            last.FlipPathBetween(v1, v2);
            innerChildren = innerChildren.Skip(pos).Concat(innerChildren.Take(pos)).ToList();
        }

        public void MakeDumbbellWith(Blossom pair, Edge edge)
        {
            this.treeLevel = TreeLevel.DUMBBELL;
            pair.treeLevel = TreeLevel.DUMBBELL;
            this.treeParentBlossom = pair;
            pair.treeParentBlossom = this;
            this.treeParentEdge = edge;
            pair.treeParentEdge = edge;
        }

        public void ConnectToTree(Blossom parent, Edge parentEdge)
        {
            treeLevel = TreeLevel.ODD;
            treeChildren.AddLast(treeParentBlossom);
            treeParentBlossom.treeLevel = TreeLevel.EVEN;
            treeParentBlossom = parent;
            treeParentEdge = parentEdge;
            treeParentBlossom.treeChildren.AddLast(this);
        }

        public Blossom MakeBlossomWith(Blossom pair, Edge pairEdge)
        {
            LinkedList<Blossom> ourPath = new LinkedList<Blossom>();
            LinkedList<Blossom> pairPath = new LinkedList<Blossom>();
            ourPath.AddLast(this);
            pairPath.AddLast(pair);
            while (ourPath.Last.Value.treeParentBlossom != null)
            {
                ourPath.AddLast(ourPath.Last.Value.treeParentBlossom);
            }
            while (pairPath.Last.Value.treeParentBlossom != null)
            {
                pairPath.AddLast(pairPath.Last.Value.treeParentBlossom);
            }
            Blossom LCA = null;
            while (ourPath.Count > 0 && pairPath.Count > 0 && ourPath.Last.Value == pairPath.Last.Value)
            {
                LCA = ourPath.Last.Value;
                ourPath.RemoveLast();
                pairPath.RemoveLast();
            }
            Blossom newBlossom = new Blossom
            {
                treeParentBlossom = LCA.treeParentBlossom,
                treeParentEdge = LCA.treeParentEdge
            };
            if (newBlossom.treeParentBlossom != null)
            {
                newBlossom.treeParentBlossom.treeChildren.Remove(LCA);
                newBlossom.treeParentBlossom.treeChildren.AddLast(newBlossom);
            }
            newBlossom.innerChildren.Add(LCA);
            Blossom previous = LCA;
            foreach (var p in ourPath.Reverse())
            {
                newBlossom.innerChildren.Add(p);
                previous.nextBlossomEdge = p.treeParentEdge;
                previous = p;
            }
            previous.nextBlossomEdge = pairEdge;
            foreach (var p in pairPath)
            {
                newBlossom.innerChildren.Add(p);
                p.nextBlossomEdge = p.treeParentEdge;
            }
            foreach (var inner in newBlossom.innerChildren)
            {
                inner.outwardBlossom = newBlossom;
            }
            foreach (var inner in newBlossom.innerChildren)
            {
                foreach (var child in inner.treeChildren)
                {
                    if (child.outwardBlossom == null)
                    {
                        newBlossom.treeChildren.AddLast(child);
                        child.treeParentBlossom = newBlossom;
                    }
                }
            }
            newBlossom.outwardBlossom = null;
            if (LCA.treeParentEdge == null)
            {
                return newBlossom;
            }
            return null;
        }

        public void DisassembleBlossom()
        {
            Edge childEdge = treeChildren.First.Value.treeParentEdge;
            Blossom parentInner;
            if (treeParentEdge.V1.GetOutermostBlossom() == this)
            {
                parentInner = GetInnerBlossomContaining(treeParentEdge.V1);
            }
            else
            {
                parentInner = GetInnerBlossomContaining(treeParentEdge.V2);
            }
            int pos = innerChildren.FindIndex(c => c == parentInner);
            int N = innerChildren.Count;
            int start = 0;
            int end = pos;
            int diff = 1;
            int ediff = 0;
            int stem = 0;
            if (pos % 2 == 1)
            {
                start = pos;
                end = stem = N;
                diff = ediff = -1;
            }
            for (int i = start; i <= end; i++)
            {
                innerChildren[i % N].treeLevel = (i % 2 == stem % 2) ? TreeLevel.ODD : TreeLevel.EVEN;
                innerChildren[i % N].treeParentBlossom = (i == pos) ? treeParentBlossom : innerChildren[i + diff];
                innerChildren[i % N].treeParentEdge = (i == pos) ? treeParentEdge : innerChildren[i + ediff].nextBlossomEdge;
                innerChildren[i % N].treeChildren.Clear();
                innerChildren[i % N].treeChildren.AddLast((i == stem) ? treeChildren.First.Value : innerChildren[(i - diff) % N]);
            }
            treeParentBlossom.treeChildren.Remove(this);
            treeParentBlossom.treeChildren.AddLast(innerChildren[pos]);
            treeChildren.First.Value.treeParentBlossom = innerChildren[0];
            Blossom thiscopy = innerChildren[0].outwardBlossom;
            foreach (var inner in innerChildren)
            {
                inner.outwardBlossom = null;
            }
            for (int i = (pos % 2 == 0) ? pos + 1 : 1; (pos % 2 == 0) ? i < N : i < pos; i += 2)
            {
                innerChildren[i].treeChildren.Clear();
                innerChildren[i + 1].treeChildren.Clear();
                innerChildren[i].treeParentBlossom = null;
                innerChildren[i + 1].treeParentBlossom = null;
                innerChildren[i].MakeDumbbellWith(innerChildren[i + 1], innerChildren[i].nextBlossomEdge);
            }
        }

        public virtual double GetMaxNegativeCharge()
        {
            return Charge;
        }

        public bool UpdateTree()
        {
            foreach (var child in treeChildren)
            {
                if (child.UpdateTree())
                {
                    return true;
                }
            }
            if (GetMaxNegativeCharge() == 0 && TreeLevel == TreeLevel.ODD)
            {
                DisassembleBlossom();
                return true;
            }
            return false;
        }

        public virtual void UpdateVertexTotal(double delta)
        {
            foreach (var inner in innerChildren)
            {
                inner.UpdateVertexTotal(delta);
            }
        }

        private double charge;
        private TreeLevel treeLevel;
        private Blossom treeParentBlossom;
        private Edge treeParentEdge;
        private LinkedList<Blossom> treeChildren = new LinkedList<Blossom>();
        private Blossom outwardBlossom;
        private List<Blossom> innerChildren = new List<Blossom>();
        private Edge nextBlossomEdge;
    }

    public class Vertex : Blossom
    {
        public Vertex(int _id) : base()
        {
            this.id = _id;
            this.totalCharge = 0;
        }
        public double TotalCharge => totalCharge;

        public override double GetMaxNegativeCharge()
        {
            return double.PositiveInfinity;
        }

        public override void UpdateVertexTotal(double delta)
        {
            totalCharge += delta;
        }

        public override Vertex GetStem()
        {
            return this;
        }

        public readonly int id;
        private double totalCharge;
    }

    public class Edge
    {
        public Edge(EdmondsMatching edmondsMatching, Vertex v1, Vertex v2, double weight)
        {
            this.edmondsMatching = edmondsMatching;
            this.v1 = v1;
            this.v2 = v2;
            this.weight = weight;
            this.matched = false;
        }

        public Vertex V1 => v1;
        public Vertex V2 => v2;

        public double GetMaxCharge()
        {
            var outer1 = v1.GetOutermostBlossom();
            var outer2 = v2.GetOutermostBlossom();
            if (outer1 == outer2)
            {
                return double.PositiveInfinity;
            }
            double reserve = weight - v1.TotalCharge - v2.TotalCharge;
            if (IsBetweenDumbbells(outer1, outer2))
            {
                return double.PositiveInfinity;
            }
            if (IsBetweenEvenAndDumbbell(outer1, outer2))
            {
                return reserve;
            }
            if (IsBetweenEvenBlossoms(outer1, outer2))
            {
                return reserve / 2;
            }
            reserve = double.PositiveInfinity;
            if (outer1.TreeLevel == TreeLevel.ODD)
            {
                reserve = Math.Min(reserve, outer1.GetMaxNegativeCharge());
            }
            if (outer2.TreeLevel == TreeLevel.ODD)
            {
                reserve = Math.Min(reserve, outer2.GetMaxNegativeCharge());
            }
            return reserve;
        }

        public bool Update()
        {
            if (GetMaxCharge() > 0)
            {
                return false;
            }
            var outer1 = v1.GetOutermostBlossom();
            var outer2 = v2.GetOutermostBlossom();
            if (IsBetweenEvenAndDumbbell(outer1, outer2))
            {
                if (outer1.TreeLevel == TreeLevel.DUMBBELL)
                {
                    outer1.ConnectToTree(outer2, this);
                }
                else
                {
                    outer2.ConnectToTree(outer1, this);
                }
                return true;
            }
            if (IsBetweenEvenBlossoms(outer1, outer2))
            {
                var root1 = outer1.GetRootBlossom();
                var root2 = outer2.GetRootBlossom();
                if (root1 == root2)
                {
                    Blossom newRoot = outer1.MakeBlossomWith(outer2, this);
                    if (newRoot != null)
                    {
                        edmondsMatching.RemoveRootFromForest(root1);
                        edmondsMatching.AddRootToForest(newRoot);
                    }
                }
                else
                {
                    outer1.FlipPathAndDisassemble(v1);
                    outer2.FlipPathAndDisassemble(v2);
                    edmondsMatching.RemoveRootFromForest(root1);
                    edmondsMatching.RemoveRootFromForest(root2);
                    outer1.MakeDumbbellWith(outer2, this);
                    this.Flip();
                    edmondsMatching.IncreaseMatchingSize();
                }
                return true;
            }
            return true;
        }

        public void Flip()
        {
            matched = !matched;
        }

        public bool IsMatched()
        {
            return matched;
        }

        public double GetWeight()
        {
            return weight;
        }

        private EdmondsMatching edmondsMatching;
        private Vertex v1;
        private Vertex v2;
        private double weight;
        private bool matched;

        private bool IsBetweenDumbbells(Blossom outer1, Blossom outer2)
        {
            return (outer1.TreeLevel == TreeLevel.DUMBBELL && outer2.TreeLevel == TreeLevel.DUMBBELL);
        }

        private bool IsBetweenEvenBlossoms(Blossom outer1, Blossom outer2)
        {
            return (outer1.TreeLevel == TreeLevel.EVEN && outer2.TreeLevel == TreeLevel.EVEN);
        }

        private bool IsBetweenEvenAndDumbbell(Blossom outer1, Blossom outer2)
        {
            return ((outer1.TreeLevel == TreeLevel.DUMBBELL && outer2.TreeLevel == TreeLevel.EVEN) || (outer1.TreeLevel == TreeLevel.EVEN && outer2.TreeLevel == TreeLevel.DUMBBELL));
        }
    }

    public class EdmondsMatching
    {
        public EdmondsMatching(int numberOfVertices)
        {
            this.numberOfVertices = numberOfVertices;
            this.matchingSize = 0;
            vertices.Capacity = numberOfVertices;
            for (int i = 0; i < numberOfVertices; i++)
            {
                vertices.Add(new Vertex(i));
                roots.AddLast(vertices[vertices.Count - 1]);
            }
        }

        public void AddEdge(int v1id, int v2id, double weight)
        {
            Vertex v1 = vertices[v1id];
            Vertex v2 = vertices[v2id];
            edges.Add(new Edge(this, v1, v2, weight));
        }

        public bool FindMinimumWeightMatching()
        {
            while (true)
            {
                double min_reserve = double.PositiveInfinity;
                foreach (var edge in edges)
                {
                    double edge_reserve = edge.GetMaxCharge();
                    min_reserve = Math.Min(min_reserve, edge_reserve);
                }
                foreach (var root in roots)
                {
                    root.UpdateCharge(min_reserve);
                }
                bool change = false;
                while (true)
                {
                    bool round = false;
                    foreach (var root in roots)
                    {
                        if (root.UpdateTree())
                        {
                            round = change = true;
                            break;
                        }
                    }
                    if (round)
                    {
                        continue;
                    }
                    foreach (var edge in edges)
                    {
                        if (edge.Update())
                        {
                            round = change = true;
                            break;
                        }
                    }
                    if (round)
                    {
                        continue;
                    }
                    break;
                }
                if (!change && min_reserve == 0)
                {
                    return false;
                }
                if (matchingSize * 2 == numberOfVertices)
                {
                    return true;
                }
                if (min_reserve == double.PositiveInfinity)
                {
                    return false;
                }
            }
        }

        public void RemoveRootFromForest(Blossom root)
        {
            roots.Remove(root);
        }

        public void AddRootToForest(Blossom root)
        {
            roots.AddLast(root);
        }

        public void IncreaseMatchingSize()
        {
            matchingSize += 1;
        }

        public double GetMatchingWeight()
        {
            double weight = 0;
            foreach (var edge in edges)
            {
                if (edge.IsMatched())
                {
                    weight += edge.GetWeight();
                }
            }
            return weight;
        }

        public List<Tuple<int, int>> GetMatchedEdges()
        {
            return edges.Where(e => e.IsMatched()).Select(e => Tuple.Create(e.V1.id, e.V2.id)).ToList();
        }

        private int matchingSize;
        private int numberOfVertices;
        private List<Vertex> vertices = new List<Vertex>();
        private List<Edge> edges = new List<Edge>();
        private LinkedList<Blossom> roots = new LinkedList<Blossom>();
    }
}

public class PriorityQueue<TKey, TValue>
{
    SortedDictionary<TKey, Stack<TValue>> dict = new SortedDictionary<TKey, Stack<TValue>>();
    int count;

    public int Count
    {
        get
        {
            return count;
        }
    }

    public void Enqueue(TKey key, TValue value)
    {
        Stack<TValue> set;
        if (!dict.TryGetValue(key, out set))
        {
            set = new Stack<TValue>();
            dict[key] = set;
        }

        set.Push(value);
        count++;
    }

    public KeyValuePair<TKey, TValue> Dequeue()
    {
        var queue = dict.First();
        if (queue.Value.Count <= 1)
        {
            dict.Remove(queue.Key);
        }

        var val = queue.Value.Pop();
        count--;
        return new KeyValuePair<TKey, TValue>(queue.Key, val);
    }

    public KeyValuePair<TKey, TValue> Peek()
    {
        var queue = dict.First();
        var val = queue.Value.Peek();
        return new KeyValuePair<TKey, TValue>(queue.Key, val);
    }
}

public struct Point
{
    public int X;
    public int Y;

    public Point(Point p)
    {
        X = p.X;
        Y = p.Y;
    }

    public Point(int x, int y)
    {
        X = x;
        Y = y;
    }

    public static bool operator ==(Point a, Point b)
    {
        return (a.X == b.X && a.Y == b.Y);
    }

    public static bool operator !=(Point a, Point b)
    {
        return !(a == b);
    }

    //objと自分自身が等価のときはtrueを返す
    public override bool Equals(object obj)
    {
        if (!(obj is Point))
        {
            return false;
        }

        Point p = (Point)obj;
        return (X == p.X && Y == p.Y);
    }

    //Equalsがtrueを返すときに同じ値を返す
    public override int GetHashCode()
    {
        return (X << 16) ^ Y;
    }

    public Point Clone()
    {
        return new Point(X, Y);
    }

    public void Reverse()
    {
        X = -X;
        Y = -Y;
    }

    public static Point operator +(Point a, Point b)
    {
        return new Point(a.X + b.X, a.Y + b.Y);
    }

    public static Point operator -(Point a, Point b)
    {
        return new Point(a.X - b.X, a.Y - b.Y);
    }

    public static Point operator *(Point a, int i)
    {
        return new Point(a.X * i, a.Y * i);
    }

    public static Point operator /(Point a, int i)
    {
        return new Point(a.X / i, a.Y / i);
    }
    public static Point operator +(Point a)
    {
        return new Point(+a.X, +a.Y);
    }

    public static Point operator -(Point a)
    {
        return new Point(-a.X, -a.Y);
    }

    public override string ToString()
    {
        return string.Format("({0},{1})", X, Y);
    }

    public string AsAnswer()
    {
        return string.Format("{0} {1}", X, Y);
    }

    public int Norm2()
    {
        return X * X + Y * Y;
    }

    public int Distance2(Point that)
    {
        return (that - this).Norm2();
    }
}

public struct Edge
{
    public readonly int Start;
    public readonly int End;
    public readonly double Weight;

    public Edge(int v0, int v1, double w)
    {
        Start = v0;
        End = v1;
        Weight = w;
    }

    public override string ToString()
    {
        return $"{Start} {End} {Weight}";
    }
}

public class Graph
{
    // Prim法により最小全域木を求める
    public static List<Edge>[] GetMinSpanningTree(Edge[][] edges, int startVertex = 0)
    {
        var treeEdges = Enumerable.Range(0, edges.Length).Select(_ => new List<Edge>()).ToArray();
        var treeVertex = new HashSet<int>() { startVertex };
        var nearEdges = new PriorityQueue<double, Edge>();
        foreach (var e in edges[startVertex])
        {
            nearEdges.Enqueue(e.Weight, e);
        }

        while (nearEdges.Count > 0)
        {
            var edge = nearEdges.Dequeue().Value;
            if (treeVertex.Contains(edge.End))
            {
                continue;
            }

            treeEdges[edge.Start].Add(edge);
            treeEdges[edge.End].Add(new Edge(edge.End, edge.Start, edge.Weight));
            treeVertex.Add(edge.End);
            foreach (var e in edges[edge.End])
            {
                nearEdges.Enqueue(e.Weight, e);
            }
        }

        return treeEdges;
    }

    // Edmondsの花分解により最小重み完全マッチングを求める
    public static List<Edge> GetMinWeightMatching(Edge[][] edges, IList<int> vertexes)
    {
        var n = vertexes.Count;
        var matching = new Edmonds.EdmondsMatching(n);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i == j)
                {
                    continue;
                }

                matching.AddEdge(i, j, edges[vertexes[i]][vertexes[j]].Weight);
            }
        }

        matching.FindMinimumWeightMatching();
        var minEdges = matching.GetMatchedEdges();
        return minEdges.Select(e => edges[vertexes[e.Item1]][vertexes[e.Item2]]).ToList();
    }

    // オイラー路を求める graphは消去される
    public static List<int> EulerTour(List<Edge>[] graph, int current = 0)
    {
        var path = new List<int> { current };
        if (graph[current].Count == 1)
        {
            while (graph[current].Count == 1)
            {
                var next = graph[current].First().End;
                graph[current].RemoveAt(0);
                graph[next].Remove(graph[next].First(e => e.End == current));
                path.Add(next);
                current = next;
            }
        }

        if (graph[current].Count > 1)
        {
            var pathToEnd = new List<int>();
            while (graph[current].Count > 0)
            {
                var next = graph[current].First().End;
                graph[current].RemoveAt(0);
                graph[next].Remove(graph[next].First(e => e.End == current));
                var nextPath = EulerTour(graph, next);
                if (nextPath.Last() != current)
                {
                    pathToEnd = nextPath;
                }
                else
                {
                    path.AddRange(nextPath);
                }
            }
            path.AddRange(pathToEnd);
        }

        return path;
    }
}

public class Solver
{
    public Point[] Planets;
    public Point[] Stations;
    public List<int> Way;
    public Stopwatch Sw;

    Random Random = new Random();

    public Solver(Point[] planets, Stopwatch sw)
    {
        Planets = planets;
        Stations = new Point[M];
        Sw = sw;
    }

    Point GetPoint(int id)
    {
        if (id < N)
        {
            return Planets[id];
        }
        return Stations[id - N];
    }

    long[,] Cost;

    void InitCost()
    {
        Cost = new long[N + M, N + M];
        for (int i = 0; i < N + M; i++)
        {
            for (int j = i + 1; j < N + M; j++)
            {
                var c = CalcCost(i, j);
                Cost[i, j] = Cost[j, i] = c;
            }
        }
    }

    long CalcCost(int start, int goal)
    {
        var cost = GetPoint(start).Distance2(GetPoint(goal));
        if (start < N)
        {
            cost *= Alpha;
        }
        if (goal < N)
        {
            cost *= Alpha;
        }
        return cost;
    }

    (long[] distance, int[] prev) Dijkstra(int start)
    {
        var d = new long[N + M];
        Array.Fill(d, long.MaxValue);
        var prev = new int[N + M];

        d[start] = 0;
        var q = new PriorityQueue<long, int>();
        q.Enqueue(0, start);

        while (q.Count > 0)
        {
            var t = q.Dequeue();
            var u = t.Value;
            if (t.Key > d[u])
            {
                continue;
            }
            for (int v = 0; v < N + M; v++)
            {
                if (u == v)
                {
                    continue;
                }
                var len = Cost[u, v];
                if (len == int.MaxValue)
                {
                    continue;
                }
                if (d[v] > d[u] + len)
                {
                    d[v] = d[u] + len;
                    q.Enqueue(d[v], v);
                    prev[v] = u;
                }
            }
        }
        return (d, prev);
    }

    (long[][] distance, int[][] prevs) CalcAllDistance()
    {
        var distance = new long[N + M][];
        var prevs = new int[N + M][];
        for (int i = 0; i < N + M; i++)
        {
            (distance[i], prevs[i]) = Dijkstra(i);
        }
        return (distance, prevs);
    }

    void InitStations()
    {
        var bestSocre = double.MaxValue;
        for (int i = 0; i < 10; i++)
        {
            (var stations, var score) = GenerateStations();
            if (score < bestSocre)
            {
                bestSocre = score;
                Stations = stations;
            }
        }
    }

    (Point[], double) GenerateStations()
    {
        // k-means
        var clusters = Enumerable.Range(0, M).Select(_ => new List<int>()).ToArray();
        for (int i = 0; i < N; i++)
        {
            clusters[Random.Next(M)].Add(i);
        }

        var update = true;
        PointD[] means = null;
        double score = 0;
        while (update && Sw.ElapsedMilliseconds < 100)
        {
            score = 0;
            means = clusters.Select(c => c.Select(i => Planets[i]).Average2()).ToArray();
            for (int i = 0; i < M; i++)
            {
                if (means[i].X < 0)
                {
                    means[i] = new PointD(Planets[Random.Next(N)]);
                }
            }
            var nextClusters = Enumerable.Range(0, M).Select(_ => new List<int>()).ToArray();
            for (int i = 0; i < N; i++)
            {
                var p = Planets[i];
                var nearest = Enumerable.Range(0, M).OrderBy(m => means[m].Distance2(p)).First();
                score += means[nearest].Distance2(p);
                nextClusters[nearest].Add(i);
            }

            update = false;
            for (int i = 0; i < M; i++)
            {
                if (!clusters[i].SequenceEqual(nextClusters[i]))
                {
                    update = true;
                    break;
                }
            }

            if (!update)
            {
                break;
            }
            clusters = nextClusters;
        }

        return (means.Select(p => p.Round()).ToArray(), score);
    }

    public void SolveByNearestNeighbor()
    {
        InitStations();
        InitCost();

        var distance = new long[N + M][];
        var prevs = new int[N + M][];
        var remain = Enumerable.Range(1, N + M - 1).ToList();
        var path = new List<int>() { 0 };

        while (remain.Count > 0)
        {
            var last = path.Last();
            (var d, var prev) = Dijkstra(last);

            var min = remain.OrderBy(i => d[i]).First();
            var way = new Stack<int>();
            for (int i = min; i != last; i = prev[i])
            {
                way.Push(i);
            }
            foreach (var i in way)
            {
                path.Add(i);
            }
            remain.Remove(min);
        }
        {
            var last = path.Last();
            (var d, var prev) = Dijkstra(last);
            var way = new Stack<int>();
            for (int i = 0; i != last; i = prev[i])
            {
                way.Push(i);
            }
            foreach (var i in way)
            {
                path.Add(i);
            }
        }

        Way = path;
    }

    public void Solve()
    {
        InitStations();
        InitCost();

        (var distance, var prevs) = CalcAllDistance();

        var edges = Enumerable.Range(0, N).Select(_ => new Edge[N]).ToArray();
        for (int i = 0; i < N; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                var d = distance[i][j];
                edges[i][j] = new Edge(i, j, d);
                edges[j][i] = new Edge(j, i, d);
            }
        }

        var mst = Graph.GetMinSpanningTree(edges);
        var oddVertexes = Enumerable.Range(0, edges.Length).Where(i => mst[i].Count % 2 == 1).ToList();
        var minMatches = Graph.GetMinWeightMatching(edges, oddVertexes);
        var graph = mst;
        foreach (var e in minMatches)
        {
            graph[e.Start].Add(e);
            graph[e.End].Add(new Edge(e.End, e.Start, e.Weight));
        }
        var eulerCycle = Graph.EulerTour(graph);
        Optimize(edges, ref eulerCycle);

        var path = new List<int>() { 0 };
        for (int t = 0; t < eulerCycle.Count - 1; t++)
        {
            var u = eulerCycle[t];
            var v = eulerCycle[t + 1];
            var way = new Stack<int>();
            for (int i = v; i != u; i = prevs[u][i])
            {
                way.Push(i);
            }
            foreach (var i in way)
            {
                path.Add(i);
            }
        }

        Way = path;
    }

    public void Optimize(Edge[][] edges, ref List<int> path)
    {
        const int limit = 900;
        long lap = 300;
        var update = true;
        while (update)
        {
            if (Sw.ElapsedMilliseconds + lap > limit)
            {
                break;
            }

            update = TwoOpt(edges, ref path);
            //update |= ThreeOpt(edges, ref path);
        }
    }

    public static bool TwoOpt(Edge[][] edges, ref List<int> path)
    {
        bool result = false;
        var ps = path;
        Func<int, int, double> distance = (s, e) =>
        {
            return edges[ps[s]][ps[e]].Weight;
        };
        var n = path.Count;
        bool updated = true;
        while (updated)
        {
            updated = false;

            for (int i = 0; i < n - 2; i++)
            {
                for (int j = i + 2; j < n - 1; j++)
                {
                    if (distance(i, i + 1) + distance(j, j + 1) > distance(i, j) + distance(i + 1, j + 1))
                    {
                        // i+1 <= x <= j を逆順にする
                        var a = ps.Take(i + 1);
                        var b = ps.Skip(i + 1).Take(j - i).Reverse();
                        var c = ps.Skip(j + 1);
                        ps = a.Concat(b).Concat(c).ToList();
                        updated = true;
                        result = true;
                    }
                }
            }
        }
        path = ps;
        return result;
    }

    public static bool ThreeOpt(Edge[][] edges, ref List<int> path)
    {
        bool result = false;
        var ps = path;
        Func<int, int, double> distance = (s, e) =>
        {
            return edges[ps[s]][ps[e]].Weight;
        };
        var n = path.Count;
    start:
        for (int i = 0; i < n - 3; i++)
        {
            for (int j = i + 1; j < n - 2; j++)
            {
                for (int k = j + 1; k < n - 1; k++)
                {
                    var d = new double[5];
                    d[0] = distance(i, i + 1) + distance(j, j + 1) + distance(k, k + 1); // original
                    d[1] = distance(i, j) + distance(i + 1, k) + distance(j + 1, k + 1);
                    d[2] = distance(i, j + 1) + distance(k, j) + distance(i + 1, k + 1);
                    d[3] = distance(i, j + 1) + distance(k, i + 1) + distance(j, k + 1);
                    d[4] = distance(i, k) + distance(j + 1, i + 1) + distance(j, k + 1);

                    var min = d.Min();
                    var minCase = Array.IndexOf(d, min);

                    if (minCase == 0)
                    {
                        continue;
                    }
                    switch (minCase)
                    {
                        case 1:
                            ps = ps.Take(i + 1).Concat(ps.Take(j + 1).Skip(i + 1).Reverse()).Concat(ps.Take(k + 1).Skip(j + 1).Reverse()).Concat(ps.Skip(k + 1)).ToList();
                            break;
                        case 2:
                            ps = ps.Take(i + 1).Concat(ps.Take(k + 1).Skip(j + 1)).Concat(ps.Take(j + 1).Skip(i + 1).Reverse()).Concat(ps.Skip(k + 1)).ToList();
                            break;
                        case 3:
                            ps = ps.Take(i + 1).Concat(ps.Take(k + 1).Skip(j + 1)).Concat(ps.Take(j + 1).Skip(i + 1)).Concat(ps.Skip(k + 1)).ToList();
                            break;
                        case 4:
                            ps = ps.Take(i + 1).Concat(ps.Take(k + 1).Skip(j + 1).Reverse()).Concat(ps.Take(j + 1).Skip(i + 1)).Concat(ps.Skip(k + 1)).ToList();
                            break;
                    }
                    result = true;
                    goto start;
                }
            }
        }
        path = ps;
        return result;
    }

    public string GetAnswer()
    {
        var buff = new StringBuilder();
        foreach (var p in Stations)
        {
            buff.AppendLine(p.AsAnswer());
        }
        buff.AppendLine(Way.Count.ToString());
        foreach (var i in Way)
        {
            var type = i < N ? TypePlanet : TypeStation;
            var index = (i < N ? i : i - N) + 1;
            buff.AppendLine($"{type} {index}");
        }
        return buff.ToString();
    }
}

public static class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var points = new Point[N];
        for (int i = 0; i < N; i++)
        {
            vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            points[i] = new Point(vals[0], vals[1]);
        }
        var sw = Stopwatch.StartNew();

        var solver = new Solver(points, sw);
        solver.Solve();
        Console.Write(solver.GetAnswer());
    }
}