/*
# 问题分析
题设给定一个链表头, 总节点个数, 反转长度, 要求按照指定方式反转链表。
指定反转方式为: 按照给定的反转长度将链表分组, 反转每一组里的元素（如果最后一组元素不足则不反转）
注意, 需要每一组反转后的末尾元素连接下一组反转后的首个元素。
由于该题是通过输入校验, 所以如果在考试中, 为了追求更快获得正确解, 可以选择直接按照指定方式输出各个节点信息的方式。
比如: 将各个链表元素按照连接顺序放入连续的数组中, 然后按照划分反转好每一个元素, 最后直接按照要求输出。
 
# 完整描述步骤
1. 获取输入: 链表头节点地址, 总节点个数, 分组长度
2. 按照链表连接顺序, 将各个节点放入连续数组中, 并计算链表长度
3. 按照指定分组长度划分排列的数组, 对于每一个满足长度要求的分组:
    - 反转数组的元素
4. 按照反转后的数组顺序输出各个节点的地址, 数据以及节点所在位置的下一个位置的元素的地址:
    - 如果是最后一个元素, 则输出"{该元素的地址} {数据} -1"
 
# 伪代码描述
1. get input: head, node_amount, group_size
2. put linked list into array, and calcualte length of array
3. calculate group_amount = length(array) / group_size;
4. for group_index in range(0, group_amount):
    - reverse array from group_index * group_size to (group_index+1) * group_size
5. for index in range(0, length(array)):
    - if index != length(array) - 1:
        - print("{array[i].address} {array[i].data} {array[i+1].address}");
    - else:
        - print("{array[i].address} {array[i].data} -1");
 
# 注意事项
1. 测试点6答案错误:
    - 需要注意给定的结点并不是全在给定链表头所在的链表上的
    - 需要按照给定的链表头进行依次遍历求出链表的长度。
2. 测试点5运行时错误:
    - 反转数组的时候下标关系式写错, 导致数组访问越界
*/
 
 
# include<stdio.h>
 
typedef struct {
    int address;
    int data;
    int next;
} node;
 
node nodes[100000];
int addresses[100000];
int data[100000];
 
void reverse_numbers(int *numbers, int start_index, int end_index){
    int result[end_index - start_index];
    for (int i = start_index; i < end_index; i++){
        result[i-start_index] = numbers[end_index - 1 - (i-start_index)];
    }
 
    for (int i = start_index; i < end_index; i++){
        numbers[i] = result[i-start_index];
    }
}
 
int main(){
    int head, node_amount, group_size;
    scanf("%d %d %d", &head, &node_amount, &group_size);
 
    int address;
    for (int i = 0; i < node_amount; i++){
        scanf("%d ", &address);
        scanf("%d %d", &nodes[address].data, &nodes[address].next);
    }
 
    
    node_amount = 0;
    int current_address = head;
    while (current_address != -1){
        node_amount++;
        current_address = nodes[current_address].next;
    }
 
 
    current_address = head;
    for (int i = 0; i < node_amount; i++){
        addresses[i] = current_address;
        data[i] = nodes[current_address].data;
        current_address = nodes[current_address].next;
    }
 
    int group_amount = node_amount / group_size;
    for (int i = 0; i < group_amount; i++){
        reverse_numbers(addresses, i*group_size, (i+1)*group_size);
        reverse_numbers(data, i*group_size, (i+1)*group_size);
    }
 
    int next;
    for (int i = 0; i < node_amount; i++){
        if (i == node_amount - 1){
            printf("%05d %d -1\n", addresses[i], data[i]);
        } else {
            printf("%05d %d %05d\n", addresses[i], data[i], addresses[i+1]);
        }
    }
 
    return 0;
}