There are three traversal methods commonly used in compilers and calculators:

     prefix
     infix
     postfix

For example, a single expression can be written in each form

     infix:    a + b * c
     prefix:   + a * b c
     postfix:  a b c * +

Note that prefix and postfix ARE NOT mirror images of each other! The advantage of prefix and postfix notations is that parentheses are unnecessary to prevent ambiguity.

In our traversal the following symbols are operators with precedence rules going from highest to lowest:

#include <stdio.h>
char infix[105], prefix[105];
int idx;
void dfs(int l, int r) {
    if(l > r)   return;
    char p = prefix[idx], i;
    idx++;
    for(i = l; i <= r; i++)
        if(infix[i] == p)
            break;
    dfs(l, i-1);
    dfs(i+1, r);
    printf(" %c", p);
}
int main() {
    while(gets(infix)) {
        gets(prefix);
        int i, j;
        for(i = 0, j = 0; infix[i]; i++) {
            if(infix[i] != ' ')
                infix[j++] = infix[i];
        }
        infix[j] = '\0';
        for(i = 0, j = 0; prefix[i]; i++) {
            if(prefix[i] != ' ')
                prefix[j++] = prefix[i];
        }
        prefix[j] = '\0';
        printf("INFIX   =>");
        for(i = 0; infix[i]; i++)
            printf(" %c", infix[i]);
        puts("");
        printf("PREFIX  =>");
        for(i = 0; prefix[i]; i++)
            printf(" %c", prefix[i]);
        puts("");
        printf("POSTFIX =>");
        idx = 0;
        dfs(0, j-1);
        puts("");
    }
    return 0;
}

Input

You are given two strings. The first string is the infix version of the expression. The second string is the prefix version of the expression. Determine the postfix version of the expression and print it out on a single line.

All input will be single characters separated by a space.

Output

Output must be the same, single characters separated by a space. There are no special sentinels identifying the end of the data.

Sample Input

a + b - c
+ a - b c

Sample Input

INFIX   => a + b - c
PREFIX  => + a - b c
POSTFIX => a b c - +

#include <stdio.h>
char infix[105], prefix[105];
int idx;
void dfs(int l, int r) {
    if(l > r)   return;
    char p = prefix[idx], i;
    idx++;
    for(i = l; i <= r; i++)
        if(infix[i] == p)
            break;
    dfs(l, i-1);
    dfs(i+1, r);
    printf(" %c", p);
}
int main() {
    while(gets(infix)) {
        gets(prefix);
        int i, j;
        for(i = 0, j = 0; infix[i]; i++) {
            if(infix[i] != ' ')
                infix[j++] = infix[i];
        }
        infix[j] = '\0';
        for(i = 0, j = 0; prefix[i]; i++) {
            if(prefix[i] != ' ')
                prefix[j++] = prefix[i];
        }
        prefix[j] = '\0';
        printf("INFIX   =>");
        for(i = 0; infix[i]; i++)
            printf(" %c", infix[i]);
        puts("");
        printf("PREFIX  =>");
        for(i = 0; prefix[i]; i++)
            printf(" %c", prefix[i]);
        puts("");
        printf("POSTFIX =>");
        idx = 0;
        dfs(0, j-1);
        puts("");
    }
    return 0;
}