#include<bits/stdc++.h>
using namespace std;

int n;               // [1] n-二叉树的节点总数
struct stu{
    char c;          // [2] 存储当前节点的字符值（题目中为大写字母）
    int l,r;         // [3] l-当前节点的左子节点编号（0表示无左子节点）；r-当前节点的右子节点编号（0表示无右子节点）
}arr[100100];        // [4] arr数组-存储所有节点信息，下标为节点编号（题目规定编号1的节点是根节点）

// 前序遍历函数（根 → 左 → 右）
void q(int v){
    // 前序遍历规则：先访问根节点，再递归左子树，最后递归右子树
    cout<<arr[v].c;//1. 输出当前节点（根节点）
    if(arr[v].l!=0){//2. 如果存在左子节点，递归遍历左子树
        q(arr[v].l);
    }
    if(arr[v].r!=0){//3. 如果存在右子节点，递归遍历右子树
        q(arr[v].r);
    } 
}

// 中序遍历函数（左 → 根 → 右）
void z(int v){
    // 中序遍历规则：先递归左子树，再访问根节点，最后递归右子树
    if(arr[v].l!=0){//1. 如果存在左子节点，递归遍历左子树
        z(arr[v].l);
    }
    cout<<arr[v].c;//2. 输出当前节点（根节点）
    if(arr[v].r!=0){//3. 如果存在右子节点，递归遍历右子树
        z(arr[v].r);
    } 
} 

// 后序遍历函数（左 → 右 → 根）
void h(int v){
    // 后序遍历规则：先递归左子树，再递归右子树，最后访问根节点
    if(arr[v].l!=0){//1. 如果存在左子节点，递归遍历左子树
        h(arr[v].l);
    }
    if(arr[v].r!=0){//2. 如果存在右子节点，递归遍历右子树
        h(arr[v].r);
    } 
    cout<<arr[v].c;//3. 输出当前节点（根节点）
} 

int main(){
    cin>>n;  // [5] 读取二叉树的节点总数n
    for(int i=1;i<=n;i++) cin>>arr[i].c>>arr[i].l>>arr[i].r;  // [6] 读取每个节点的信息：字符值、左子节点编号、右子节点编号，存入arr数组（i为节点编号）
    
    // 执行三种遍历并输出结果
    // 前序遍历（根左右）
    q(1);  // [7] 从根节点（编号1）开始前序遍历
    cout<<endl; 
    // 中序遍历（左根右）
    z(1);  // [8] 从根节点开始中序遍历
    cout<<endl;
    // 后序遍历（左右根）
    h(1);  // [9] 从根节点开始后序遍历
    return 0;
}