#include<stdio.h>
#include<stdlib.h>
#define LAMBDA NULL

typedef char labeltype;  //oznaka cvora

typedef struct celltype{
  labeltype label;
  struct celltype *leftchild;
  struct celltype *rightchild;
}celltype;

typedef celltype *node;
typedef celltype *BinaryTree;

void BiCreate(labeltype l, BinaryTree TL, BinaryTree TR, BinaryTree *Tp){
  *Tp=(celltype*)malloc(sizeof(celltype));
  (*Tp)->label=l;
  (*Tp)->leftchild=TL;
  (*Tp)->rightchild=TR;
}

void BiMakeNull(BinaryTree *Tp){
  *Tp=NULL;
}

int BiEmpty(BinaryTree T){
  if(T==NULL) return 1;
  return 0;
}

void BiLeftSubtree(BinaryTree T, BinaryTree *TLp){
  if(BiEmpty(T))exit(8); //nije definirano
  (*TLp)=T->leftchild;
}

void BiRightSubtree(BinaryTree T, BinaryTree *TRp){
   if(BiEmpty(T))exit(8);
  (*TRp)=T->rightchild;
}

node BiInsertLeftChild(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8); //nije definirana
  if(i->leftchild!=NULL) return LAMBDA;
  BiCreate(l, NULL, NULL, (&i->leftchild));
  return i->leftchild;
}

node BiInsertRightChild(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8);  // nije definirana
  if(i->rightchild!=NULL) return LAMBDA;
  BiCreate(l, NULL, NULL, (&i->rightchild));
  return i->rightchild;
}

void BiDelete(node i, BinaryTree *Tp){
  if(i==NULL) exit(1);
  if(i->leftchild!=NULL || i->rightchild!=NULL) exit(1);
  i=NULL;
}

node BiRoot(BinaryTree T){
  if(T==NULL)
    return LAMBDA;
  return T;
}

node BiLeftChild(node i, BinaryTree T){
  if(i->leftchild==NULL)
    return LAMBDA;
  return i->leftchild;
}

node BiRightChild(node i, BinaryTree T){
  if(i->rightchild==NULL)
    return LAMBDA;
  return i->rightchild;
}

void roditelj(node *otac, node i, node kor, BinaryTree T) {  //pomocna funkcija
  if (BiLeftChild(i, T)== i || BiRightChild(i, T)== i)
    *otac = kor;
  if (*otac)
    return;
  if (BiLeftChild(i, T))
    roditelj(otac, i, BiLeftChild(i, T),T);
  if (BiRightChild(i, T))
    roditelj(otac, i, BiRightChild(i, T),T);
}

node BiParent(node i, BinaryTree T){
  if(i==NULL) exit(8);  //nije definirana
  if(i==T) return LAMBDA;
  node otac=NULL;
  roditelj(&otac, i, T, T);
  return otac;
}

labeltype BiLabel(node i, BinaryTree T){
  if(i==NULL) exit(8); //nije definirana
  return i->label;
}

void BiChangeLabel(labeltype l, node i, BinaryTree *Tp){
  if(i==NULL) exit(8); //nije definirana
  i->label=l;
}

int search(char arr[], int strt, int end, char value);

int preIndex;
BinaryTree buildTree(char in[], char pre[], int inStrt, int inEnd){
     //zadnji u postorderu je korjen

  if(inStrt > inEnd){
    return LAMBDA;
  }

  BinaryTree tNode;   //krecem se od iza zbog defiicje postordera
  BiMakeNull(&tNode);
  if(inStrt == inEnd) {
        BiCreate(pre[--preIndex], LAMBDA, LAMBDA, &tNode);
    return tNode;
    }

  BinaryTree A, B;
  BiMakeNull(&A);
  BiMakeNull(&B);

  int inIndex = search(in, inStrt, inEnd, pre[--preIndex]);
  char moj_label = pre[preIndex];
  B = buildTree(in, pre, inIndex+1, inEnd);
  A = buildTree(in, pre, inStrt, inIndex-1);
  BiCreate(moj_label, A, B, &tNode);
  return tNode;
}

int search(char arr[], int strt, int end, char value){ //pomocna funkcija za trazenje znaka
  int i;
  for(i = strt; i <= end; i++){
    if(arr[i] == value)
      return i;
  }
}


void print_tree(node cvor, BinaryTree T){
  int i;
  if(!cvor) return;
  printf ("%c", BiLabel(cvor, T));
  if (BiLeftChild(cvor, T)!=NULL) printf(" %c", BiLabel((BiLeftChild(cvor, T)), T));
  else printf (" NULL");
  if (BiRightChild(cvor, T)!=NULL) printf(" %c", BiLabel((BiRightChild(cvor, T)), T));
  else printf (" NULL");
  printf ("\n");
  print_tree(BiLeftChild(cvor, T), T);
  print_tree(BiRightChild(cvor, T), T);
}

int funkcija(char* s){
  int i=0;
  while(s[i]!='\0')i++;
  return i;
}

int main(){
  BinaryTree T;
  BiMakeNull(&T);
  char in[1000];
  char pre[1000];
  scanf("%s", in);
  scanf("%s", pre);
  /*char in[] = {'d', 'b', 'h', 'e', 'i', 'a', 'f', 'c', 'g'};
  char pre[] = {'d', 'h', 'i', 'e', 'b', 'f', 'g', 'c', 'a'}; */
  int len = funkcija(in);
  printf("%d len\n",len);
  preIndex = len;
  T = buildTree(in, pre, 0, len - 1);
  print_tree(BiRoot(T), T);
  return 0;
}