An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<=30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

6

Push 1

Push 2

Push 3

Pop

Pop

Push 4

Pop

Pop

Push 5

Push 6

Pop

Pop

Sample Output:

3 4 2 6 5 1

 #include<cstdio>

 #include<stack>

 #include<algorithm>

 #include<iostream>

 #include<stack>

 #include<set>

 #include<map>

 #include<vector>

 using namespace std;

 int per[],in[];

 stack<int> s;

 int n;

 void Build(int *per,int *in,int num){

     if(num==){

         return;

     }

     int mid=per[];

     //cout<<mid<<endl;

     int i;

     for(i=;i<num;i++){

         if(in[i]==mid){

             break;

         }

     }

     //cout<<num<<endl;

     Build(per+,in,i);

     Build(per++i,in++i,num--i);

     if(num==n){

         printf("%d",mid);

     }

     else{

         printf("%d ",mid);

     }

 }

 int main(){

     //freopen("D:\\INPUT.txt","r",stdin);

     scanf("%d",&n);

     n*=;

     int i,num,pi=,ini=;

     string op;

     for(i=;i<n;i++){

         cin>>op;

         if(op=="Push"){

             scanf("%d",&num);

             s.push(num);

             per[pi++]=num;

         }

         else{

             in[ini++]=s.top();

             s.pop();

         }

     }

     n=n/;

     /*cout<<n<<endl;

     for(i=0;i<n;i++){

         cout<<per[i]<<" ";

     }

     cout<<endl;

     for(i=0;i<n;i++){

         cout<<in[i]<<" ";

     }

     cout<<endl;*/

     Build(per,in,n);

     printf("\n");

     return ;

 }