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

typedef struct Treenode{
    char name[50];
    int score;
    struct Treenode*left;
    struct Treenode*right;
}Node;
Node*createNode(char name[],int score){
    Node*newnode = (Node*)malloc(sizeof(Node));
    strcpy(Node->name,name);
    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);
}
void preorder(Node*root){
    if(root==NULL){
        return;
    }
    printf("%d",root->data);
    preorder(root->left);
    preorder(root->right);
}
void inorder(Node*root){
    if(root==NULL){
        return ;
    }
    inorder(root->left);
    printf("%d",root->data);
    inorder("%d",root->data);
}

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