// DIN AFISARILE din SRD si SDR (inOrder si postOrder).

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

using namespace std;

struct Node{
    Node* left;
    Node* right;
    int value;
};

void readData(char* fileName, int *n, int** inValues, int** postValues){
    FILE *in = fopen(fileName, "rt");
    int i, *localInValues, *localPostValues;
    fscanf(in, "%i", n);

    localInValues = (int*)malloc(*n * sizeof(int));
    localPostValues = (int*)malloc(*n * sizeof(int));

    for(i=0; i<*n; i++)
        fscanf(in, "%i", &localInValues[i]);

    for(i=0; i<*n; i++)
        fscanf(in, "%i", &localPostValues[i]);

    *inValues = localInValues;
    *postValues = localPostValues;
}

void printArray(int* v, int n){
    int i;
    for(i=0; i<n; i++)
        printf("%i ", v[i]);

    printf("\n");
}

int findPosition(int value, int left, int right, int* inValues){
    int i;
    for(i=left; i<right; i++){
        if(inValues[i] == value)
            return i;
    }

    return -1;
}

Node* solveTask(int leftIn, int rightIn, int leftPost, int rightPost, int* inValues, int* postValues){
    if(rightIn - leftIn < 1)
        return NULL;

    Node* localNode = (Node*)malloc(sizeof(Node));
    int currentValue = postValues[rightPost-1];
    int positionOnInValues = findPosition(currentValue, leftIn, rightIn, inValues);
    if(positionOnInValues == -1){
        printf("S-a intamplat ceva naspa\n");
        exit;
    }

    localNode->value = currentValue;
    localNode->left = (Node*)malloc(sizeof(Node));
    localNode->right = (Node*)malloc(sizeof(Node));

    int rightValues = rightIn - positionOnInValues;
    int leftValues = positionOnInValues - leftIn;

    int rightSonRightPost = rightPost - 1; // aici e -1 ca trecem de radacina curenta (100 in primul exemplu)
    int rightSonLeftPost = rightPost - rightValues;
    int leftSonRightPost = rightSonLeftPost;
    int leftSonLeftPost = rightSonLeftPost - leftValues;

    localNode->left = solveTask(leftIn, positionOnInValues, leftSonLeftPost, leftSonRightPost, inValues, postValues);
    localNode->right = solveTask(positionOnInValues+1, rightIn, rightSonLeftPost, rightSonRightPost, inValues, postValues);

    return localNode;

}

void RSD(Node* root){
    if(!root)
        return;

    printf("%i ", root->value);

    if(root->left)
        RSD(root->left);
    if(root->right)
        RSD(root->right);

}

void SRD(Node* root){
    if(!root)
        return;

    if(root->left)
        SRD(root->left);

    printf("%i ", root->value);

    if(root->right)
        SRD(root->right);

}

void SDR(Node* root){
    if(!root)
        return;

    if(root->left)
        SDR(root->left);

    if(root->right)
        SDR(root->right);

    printf("%i ", root->value);


}


int main()
{
    Node* root = (Node*)malloc(sizeof(Node));

    int *inValues, *postValues, size;
    readData("in.in", &size, &inValues, &postValues);

    //printArray(postValues, size);
    root = solveTask(0, size, 0, size, inValues, postValues);

    RSD(root);
    printf("\n");
    SRD(root);
    printf("\n");
    SDR(root);

    return 0;
}