import math
import sys
import random

ALPHA = 5

class Result:
    def __init__(self, stations, travel_seq):
        self.stations = []
        for x, y in stations:
            self.stations.append(f"{x} {y}")
        self.travel_seq = []
        for t, r in travel_seq:
            self.travel_seq.append(f"{t} {r}")


def calc_score(stations, travel_seq, planets):
    # スコア計算
    S = 0
    for i in range(len(travel_seq) - 1):
        t1, r1 = travel_seq[i]
        t2, r2 = travel_seq[i + 1]
        if t1 == 2 and t2 == 2:
            x1, y1 = stations[r1 - 1]
            x2, y2 = stations[r2 - 1]
            S += ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        elif t1 == 2 and t2 == 1:
            x1, y1 = stations[r1 - 1]
            x2, y2 = planets[r2 - 1]
            S += ALPHA * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        elif t1 == 1 and t2 == 2:
            x1, y1 = planets[r1 - 1]
            x2, y2 = stations[r2 - 1]
            S += ALPHA * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
        else:
            # t1 == 1 and t2 == 1
            alpha2 = ALPHA ** 2
            x1, y1 = planets[r1 - 1]
            x2, y2 = planets[r2 - 1]
            S += alpha2 * ((x1 - x2) ** 2 + (y1 - y2) ** 2)
    print(f"S = {S}", file=sys.stderr, flush=True)

    score = (10 ** 9) / (1000 + math.sqrt(S))
    score = int(score)
    print(f"score = {score}", file=sys.stderr, flush=True)


def k_means(planets, M):
    cluser_array = [-1] * len(planets)
    for i in range(len(planets)):
        cluster_index = random.randint(0, M - 1)
        cluser_array[i] = cluster_index

    ave_x = 0.0
    ave_y = 0.0
    for x, y in planets:
        ave_x += x
        ave_y += y
    ave_x /= len(planets)
    ave_y /= len(planets)


    for _ in range(100):
        # Mステップ
        averages_x = [0] * M
        averages_y = [0] * M
        counts = [0] * M
        for i, cluster_index in enumerate(cluser_array):
            averages_x[cluster_index] += planets[i][0]
            averages_y[cluster_index] += planets[i][1]
            counts[cluster_index] += 1
        
        for i in range(M):
            if counts[i] > 0:
                averages_x[i] /= counts[i]
                averages_y[i] /= counts[i]
            else:
                averages_x[i] = ave_x
                averages_y[i] = ave_y
        
        # Eステップ
        for i, planet in enumerate(planets):
            min_distance = float("inf")
            min_cluster_index = -1
            for j in range(M):
                distance = (planet[0] - averages_x[j]) ** 2 + (planet[1] - averages_y[j]) ** 2
                if distance < min_distance:
                    min_distance = distance
                    min_cluster_index = j
            cluser_array[i] = min_cluster_index

    stations = []
    for i in range(M):
        stations.append((int(averages_x[i]), int(averages_y[i])))
    return stations


def solve(N, M, planets):
    """
    K-meansでstationの位置を最適化する
    旅行の順番を貪欲法+シミュレーテッドアニーリングで求める
    """
    random.seed(10)

    # K-meansによるstationの情報の格納
    stations = k_means(planets, M)

    # distance-matrixの計算
    energy_cost_matrix = [[float("inf") for _ in range(N + M)]  for _ in range((N + M))]
    for i in range(N + M):
        for j in range(N + M):
            if i == j:
                energy_cost_matrix[i][j] = 0
                continue

            weight = 1
            if i < N:
                x1, y1 = planets[i]
                weight *= ALPHA
            else:
                x1, y1 = stations[i - N]

            if j < N:
                x2, y2 = planets[j]
                weight *= ALPHA
            else:
                x2, y2 = stations[j - N]
                
            energy_cost_matrix[i][j] = (x1 - x2)**2 + (y1 - y2)**2
            energy_cost_matrix[i][j] *= weight

    # ワーシャルフロイド法で最短距離を求める
    next_hop_matrix = [[i for _ in range(N + M)]  for i in range((N + M))]
    for k in range(N + M):
        for i in range(N + M):
            for j in range(N + M):
                if energy_cost_matrix[i][j] > energy_cost_matrix[i][k] + energy_cost_matrix[k][j]:
                    energy_cost_matrix[i][j] = energy_cost_matrix[i][k] + energy_cost_matrix[k][j]
                    next_hop_matrix[i][j] = k
    
    # 貪欲法で初期解の生成
    travel_seq = [0]
    last_pos = 0
    passed = [False] * N
    passed[0] = True
    travel_cost = 0
    for _ in range(N - 1):
        base_cost = float("inf")
        next_pos = -1
        for j in range(N):
            if passed[j]:
                continue

            cost = energy_cost_matrix[last_pos][j]
            new_cost = travel_cost + cost
            if new_cost < base_cost:
                base_cost = new_cost
                next_pos = j

        travel_cost = base_cost       
        travel_seq.append(next_pos)
        passed[next_pos] = True
        last_pos = next_pos

    cost = energy_cost_matrix[last_pos][0]
    travel_cost += cost
    travel_seq.append(0)
    print(f"init_travel_cost: {travel_cost}", file=sys.stderr, flush=True)

    # 山登り法で最適解を探す
    for _ in range(10000):
        i = random.randint(1, N - 1)
        j = random.randint(1, N - 1)
        if i == j:
            continue
        if i > j:
            tmp = i
            i = j
            j = tmp

        new_cost = travel_cost
        new_cost -= energy_cost_matrix[travel_seq[i - 1]][travel_seq[i]]
        new_cost -= energy_cost_matrix[travel_seq[j]][travel_seq[j + 1]]
        new_cost += energy_cost_matrix[travel_seq[i - 1]][travel_seq[j]]
        new_cost += energy_cost_matrix[travel_seq[i]][travel_seq[j + 1]]
        if new_cost < travel_cost:
            travel_cost = new_cost
            for k in range(i, (i + j + 1) // 2):
                tmp = travel_seq[k]
                travel_seq[k] = travel_seq[j + i - k]
                travel_seq[j + i - k] = tmp
            
    print(f"travel_cost: {travel_cost}", file=sys.stderr, flush=True)
    new_travel_seq = []
    new_travel_seq.append((1, travel_seq[0] + 1))
    for i in range(len(travel_seq) - 1):
        i0 = travel_seq[i]
        j0 = travel_seq[i + 1]

        cur = j0
        path  = []
        while cur != i0:
            path.append(cur)
            cur = next_hop_matrix[i0][cur]
        path.reverse()
        for p in path:
            if p < N:
                new_travel_seq.append((1, p + 1))
            else:
                new_travel_seq.append((2, p - N + 1))


    calc_score(stations, new_travel_seq, planets)
    return Result(stations, new_travel_seq)

def main():
    N, M = map(int, input().split())
    planets = []
    for _ in range(N):
        a, b = map(int, input().split())
        planets.append((a, b))
    
    result = solve(N, M, planets)

    for i in range(M):    
        print(result.stations[i])
    print(len(result.travel_seq))
    for i in range(len(result.travel_seq)):
        print(result.travel_seq[i])


if __name__ == "__main__":
    main()