/*
# 问题分析
题设给定两个链表头, 总的节点数目, 要求将两个链表按指定方式合并。
指定合并方式为: 每两个长链表元素后要插入一个短链表元素, 直到短链表元素插入完毕则得到合并后的链表。
由于该题是通过输入校验, 所以如果在考试中, 为了追求更快获得正确解, 可以选择直接按照指定方式输出各个节点信息的方式。
比如: 整理好两个链表之后, 每输出两个长链表元素, 就输出一个短链表元素, 如果短链表输出完毕, 则直接输出长链表元素直到输出完毕。
 
# 完整描述步骤
1. 获取输入: 链表头一, 链表头二, 总的节点信息个数
2. 初始化统计器:
    - 链表长度一 = 0
    - 链表长度二 = 0
3. 整理链表并计算链表长度:
    - 从链表头一开始, 直到链表指针指向空地址（即, 地址为-1）, 不断累计链表长度一
    - 从链表头二开始, 直到链表指针指向空地址（即, 地址为-1）, 不断累计链表长度二
4. 如果长度一小于长度二, 则:
    - 互换链表头一和链表头二
    - 互换链表长度一和链表长度二
5. 输出"{链表一的第一个元素地址} {链表一的第一个元素数据}"
6. 对于索引位置从0到总长度(长度一+长度二):
    - 如果当前索引模3余2:
        - 如果链表二还未输出完毕:
            - 则倒着输出链表二的元素的地址, 地址, 数据
    - 否则:
        - 则输出链表一的元素的地址, 地址, 数据
7. 输出"-1"
 
# 伪代码描述
1. get input: head_1, head_2, node_amount
2. sort linked list and calculate their length:
    - nodes_1 = sorted(linked list of head_1)
    - nodes_2 = sorted(linked list of head_2)
    - length_1 = length(linked list of head_1)
    - length_2 = length(linked list of head_2)
3. if length_1 < length_2:
    - swap(length_1, length_2);
    - swap(head_1, head_2);
4. print("{nodes_1[0].address} {nodes_1[0].data}")
5. init node_indexes:
    - node_index = 1;
    - nodes_1_index = 1;
    - nodes_2_index = length_2 - 1;
6. for node_index in range(1, length_1+length_2):
    - if node_index % 3 == 2:
        - print(" {nodes_2[nodes_2_index].address}\n{nodes_2[nodes_2_index].address} {nodes_2[nodes_2_index].data}");
        - nodes_2_index--;
    - else:
        - print(" {nodes_1[nodes_1_index].address}\n{nodes_1[nodes_1_index].address} {nodes_1[nodes_1_index].data}");
        - nodes_1_index++;
7. print(" -1");
 
# 注意事项:
1. 测试点3:
    - 长链表是短链表的2倍多, 需要考虑短链表输出完毕后不再输出短链表, 只输出长链表。
*/
 
 
# include<stdio.h>
 
typedef struct {
    int address;
    int data;
    int next;
} node;
 
node nodes[100000];
 
int calcuate_linked_list_length(int head){
    int length = 0;
    int current = head;
    while (current != -1){
        length++;
        current = nodes[current].next;
    }
    return length;
}
 
int put_nodes_in_array(node *array, int head){
    int current = head;
    int node_index = 0;
    while (current != -1){
        array[node_index] = nodes[current];
        current = nodes[current].next;
        node_index++;
    }
    return 0;
}
 
int main(){
    int head_1, head_2, node_amount;
    scanf("%d %d %d", &head_1, &head_2, &node_amount);
 
    int address;
    for (int i = 0; i < node_amount; i++){
        scanf("%d", &address);
        nodes[address].address = address;
        scanf("%d %d", &nodes[address].data, &nodes[address].next);
    }
 
    int length_1 = calcuate_linked_list_length(head_1);
    int length_2 = calcuate_linked_list_length(head_2);
    if (length_1 < length_2){
        int temp = head_2;
        head_2 = head_1;
        head_1 = temp;
        temp = length_2;
        length_2 = length_1;
        length_1 = temp;
    }
 
    node nodes_1[length_1];
    put_nodes_in_array(nodes_1, head_1);
    node nodes_2[length_2];
    put_nodes_in_array(nodes_2, head_2);
 
    printf("%05d %d", nodes_1[0].address, nodes_1[0].data);
    int node_index = 1;
    for (int i = 1, j = length_2 - 1; i < length_1 || j >= 0; node_index++){
        if (node_index % 3 == 2){
            if (j == -1) continue;
            printf(" %05d\n%05d %d", nodes_2[j].address, nodes_2[j].address, nodes_2[j].data);
            j--;
        } else {
            printf(" %05d\n%05d %d", nodes_1[i].address, nodes_1[i].address, nodes_1[i].data);
            i++;
        }
    }
 
    printf(" -1");
    return 0;
}