class Node {
public:
    char data;
    Node* left;
    Node* right;

    Node(char data):data(data),left(nullptr),right(nullptr){}
};

class Tree {
public:
    Node* root;
    Tree():root(nullptr){}
    void add(char data, char left, char right) {
    	if (root == nullptr) {
    	    root = new Node(data);
    	    if (left != '.') {
    	    	root->left = new Node(left);
    	    }
    	    if (right != '.') {
    		    root->right = new Node(right);
    	    }
    	}
    	else {
    		search(root, data, left, right);
    	}
    }
    void preOrder(Node* cur) {
    	if (cur == nullptr)return;
    	cout << cur->data;
    	preOrder(cur->left);
    	preOrder(cur->right);
    }

    void postOrder(Node* cur) {
    	if (cur == nullptr)return;
    	postOrder(cur->left);
    	postOrder(cur->right);
    	cout << cur->data;
    }

    void inOrder(Node* cur) {
    	if (cur == nullptr)return;
    	inOrder(cur->left);
    	cout << cur->data;
    	inOrder(cur->right);
    }
private:
    void search(Node* root, char data, char left, char right) {
    	if (root == nullptr) {
    	    return;
    	}
    	else if (root->data == data) {
    	    if (left != '.')root->left = new Node(left);
    	    if (right != '.')root->right = new Node(right);
    	}
    	else {
    	    search(root->left, data, left, right);
    	    search(root->right, data, left, right);
    	}
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    Tree* tree = new Tree();
    for (int i = 0; i < n; i++) {
    	cin >> node >> L >> R;
    	tree->add(node, L, R);
    }
    tree->preOrder(tree->root);
    cout << '\n';
    tree->inOrder(tree->root);
    cout << '\n';
    tree->postOrder(tree->root);

    return 0;
}