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

typedef struct node{
    char name[100];
    int score;
    struct node *left;
    struct node *right;
}Node;
Node *create(char name[],int score){
    Node *newnode=(Node*)malloc(sizeof(Node));
    strcpy(newnode->name,name);
    newnode->score=score;
    newnode->left=NULL;
    newnode->right=NULL;
    return newnode;
}
Node *insert(Node *root,char name[],int score){
    if(root==NULL)
      return create(name,score);
    if(score<root->score)
      root->left=insert(root->left,name,score);
      else
      root->right=insert(root->right,name,score);
      return root;
}
void preorder(Node *root){
        if(root==NULL){
            return;
        }
        printf("%s %d ",root->name,root->score);
        preorder(root->left);
        preorder(root->right);
    }
    void inorder(Node *root){
        if(root==NULL){
            return;
        }
        inorder(root->left);
        printf("%s %d ",root->name,root->score);
        inorder(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;
        }
        char name[100];
        Node *root=NULL;
        int score;
        for(int i=0;i<n;i++){
            scanf("%s %d",name,&sore);
            root=insert(root,name,score);
        }
inorder(root);
printf("\n");
preorder(root);
printf("\n");
postorder(root);
return 0;
}