#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct TreeNode{
    char name[50];
    int score;
    struct TreeNode *left;
    struct TreeNode *right;
}Node;

Node* createNode(char name[], int score){
Node* node=(Node*)malloc(sizeof(Node));
strcpy(node->name, name);
node->score=score;
node->left=NULL;
node->right=NULL;
return node;
}

Node* insert(Node* root,char name[],int score){
    if(root==NULL)
       return createNode(name,score);
       
    if(score<root->score)
       root->left=insert(root->left, name, score);
    else
       root->right=insert(root->right, name, score);
       
       return root;
}   
       
       
void inoreder(Node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%s %d ",root->name,root->score);
    inorder(root->right);
}

void preorder(Node* root){
    if(root == NULL)return;
    printf("%s %d ", root->name, root->score);
    preorder(root->left);
    preorder(root->right);
}

void postorder(Node* root){
    if(root==NULL)return;
    postorder(root->left);
    postorder(root->right);
    printf("%s %d ", root->name, root->score);
}
int main(){
    int n;
    scanf("%d",&n);
    
    if(n<0){
        printf("Invalid input");
        return 0;
    }
    
    Node* root =NULL;
    
    for(int i=0;i<n;i++){
        char name[50];
        int score;
        scanf("%s %d", name, &score);
        root = insert(root, name, score);
    }
    
    inoreder(root);
    printf("\n");
    
    preorder(root);
    printf("\n");
    
    postorder(root);
    
    return 0;
}