// editor5
#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* newnode = (node*)malloc(sizeof(node));
    strcpy(node->name, name);
    node->score = score;
    node->left = NULL;
    node->right = NULL;
    return newnode;
}
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 inorder(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)
        
    }
    inorder(root);
    printf("\n");
    preorder(root);
    printf("\n");
    postorder(root);
    return 0;
}