/*
題意：給一個(gè)鏈表，然后給出一個(gè)K，每K個(gè)節(jié)點(diǎn)反轉(zhuǎn)一次

解題：
1、定義及靜態(tài)鏈表，order表示在鏈表中的序號(hào)，
2、初始化，令order的初值均為maxn，表示初始時(shí)所有節(jié)點(diǎn)為無(wú)效節(jié)點(diǎn)
3、由題目給出的鏈表首地址begi遍歷整條鏈表，并記錄每個(gè)有效節(jié)點(diǎn)在鏈表中的序號(hào)，統(tǒng)計(jì)技術(shù)有效節(jié)點(diǎn)的個(gè)數(shù)count。
4、對(duì)節(jié)點(diǎn)進(jìn)行排序，按節(jié)點(diǎn)order從小到大排序
5、輸出鏈表，這個(gè)很煩
將n個(gè)節(jié)點(diǎn)分塊n/k塊，枚舉這些完整的塊，從后往前輸出節(jié)點(diǎn)信息、注意每一個(gè)塊最后節(jié)點(diǎn)next的處理
（1）如果i號(hào)塊不是最后一個(gè)完整快，那么next就是（i+2)*k - 1號(hào)節(jié)點(diǎn)，也就是（i+1)號(hào)塊最后一個(gè)節(jié)點(diǎn)
（2）如果i號(hào)塊是最后一個(gè)塊，同樣有兩種情況
一、如果n%k==0，則說(shuō)明這是整個(gè)單聊表的最后一個(gè)節(jié)點(diǎn)，輸出-1
二、如果n%k不等于0，則說(shuō)明這個(gè)完整快后面還有一點(diǎn)尾巴，那么這個(gè)完整塊的最后一個(gè)節(jié)點(diǎn)的next不是下一個(gè)塊的最后一個(gè)，而是這個(gè)塊的第一個(gè)，接下來(lái)，從前往后輸出即可

learn && wrong:
1、存在無(wú)效節(jié)點(diǎn)的可能
2、反轉(zhuǎn)鏈表只改變節(jié)點(diǎn)的next地址，不改變本身地址，因此address和data是綁定的
3、%05d的輸出格式會(huì)讓-1出現(xiàn)錯(cuò)誤，所以-1要單獨(dú)輸出
4、給order排序很好
5、排序后輸出下一個(gè)節(jié)點(diǎn)，就是【i+1】.adderss就很不錯(cuò)
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;

struct Node{    //定義鏈表，步驟1
    int address,data,next;
    int order;  //節(jié)點(diǎn)在鏈表上的序號(hào)，無(wú)效節(jié)點(diǎn)為maxn
}node[maxn];

bool cmp(Node a,Node b){
    return a.order < b.order;   //按order從小到大排序
}

int main()
{
    for(int i = 0;i <maxn;i++){ //初始化（步驟2）
        node[i].order = maxn;   //  初始化全部為無(wú)效節(jié)點(diǎn)
    }

    int begin, n, K, address;
    scanf("%d%d%d", &begin, &n, &K);    //起始地址，節(jié)點(diǎn)個(gè)數(shù)、步長(zhǎng)
    for(int i = 0;i < n;i++){
        scanf("%d",&address);
        scanf("%d%d", &node[address].data, &node[address].next);
        node[address].address = address;
    }

    int p = begin, count = 0;   //count計(jì)數(shù)有效節(jié)點(diǎn)的數(shù)目

    while(p != -1){ //遍歷鏈表找出單鏈表的所有效節(jié)點(diǎn)（步驟3）
        node[p].order = count++;    //節(jié)點(diǎn)在單鏈表中的序號(hào)
        p = node[p].next;  //下一個(gè)結(jié)點(diǎn)
    }

    sort(node, node + maxn, cmp);   //按單鏈表從頭到尾順序排列（步驟4）
    //有效節(jié)點(diǎn)為前count個(gè)節(jié)點(diǎn)，為了下面書寫方便，因此把count賦給n
    n = count;
    //單鏈表已經(jīng)形成，下面是按題目要求的輸出（步驟5）
    for(int i = 0;i < n / K;i++){   //枚舉完整的n / K 塊
        for(int j = (i + 1) * K - 1;j < i * K;j--){ //第i塊倒著輸出
            printf("%05d %d %05d\n",    node[j].address, node[j].data, node[j - 1].address);
        }

        //下面是每一塊的最后一個(gè)結(jié)點(diǎn)的next地址的處理
        printf("%05d %d ", node[i * K].address, node[i * K].data);
        if(i < n / K - 1){  //如果不是最后一塊，就指向下一塊的最后一個(gè)結(jié)點(diǎn)
            printf("%05d\n", node[(i+2) * K - 1].address);
        }else{  //是最后一塊時(shí)
            if(n % K == 0){ //恰好是最后一個(gè)結(jié)點(diǎn)，輸出-1
                printf("-1\n");
            }else{  //剩下的不完整塊按原先的順序輸出
                printf("%05d\n", node[(i + 1) * K].address);
                for(int i = n / K * K;i < n;i++){
                    printf("%05d %d", node[i].address, node[i].data);
                    if(n < -1){
                        printf("%05d\n",node[i+1].address);
                    }else{
                        printf("-1\n");
                    }
                }
            }
        }
    }
    return 0;
}