8

package drzewo;

import java.util.Scanner;

public class Drzewo {

    static Scanner input = new Scanner(System.in);

    static class Node
    {
        public int info ;
        public Node left;
        public Node right ;

        public void displayNode()
        {
            System.out.println(info);
            if(left!=null)
                left.displayNode();
            if(right!=null)
                right.displayNode();
        }

        Node()
        {
            info = 0;
            left = null;
            right = null;
        }

        Node(int a, Node l, Node r)
        {
            info = a;
            left = l;
            right = r;
        }

    }

    static class Tree
    {
        private Node root = new Node(0,null,null);
        Tree()
        {
            root = null;
        }

        Tree(Node a)
        {
            root = a;
        }

        public Node korzen()
        {
            return root;
        }

        public void preorder(Node w)
        {
            if(w != null)
            {
                System.out.print(w.info+" ");
                preorder(w.left);
                preorder(w.right);
            }
        }

        public void inorder(Node w)
        {
            if(w != null)
            {
                inorder(w.left);
                System.out.print(w.info+" ");
                inorder(w.right);
            }
        }

        public void postorder(Node w)
        {
            if(w != null)
            {
                postorder(w.left);
                postorder(w.right);
                System.out.print(w.info+" ");
            }
        }

        public void insert(int id, Node a)
        {
            a.info=id;
        }

        public void newNodeL(Node p, int key)
        {
            Node a = new Node(key,null,null);
            p.left = a;
        }

        public void newNodeR(Node p, int key)
        {
            Node a = new Node(key,null,null);
            p.right = a;
        }

        public void preindrzewo(Tree T,Node w,int []tabpre, int []tabin, int poczatek, int koniec, int inpo)
        {
            int kr=inpo;
            int c=0;

            if(poczatek == 0)
            {
                Node a = new Node(tabpre[0],null,null);
                T = new Tree(a);
                w = T.korzen();
            }

            T.insert(tabpre[poczatek], w);

            if(koniec-poczatek >= 0)
                while(tabpre[poczatek] != tabin[kr+c])
                    c++;// index korzenia w tabin mamy L K P

            if(poczatek+c+1 == koniec)
                if(tabpre[poczatek+c+1]==tabin[koniec])
                    T.newNodeR(w, tabin[koniec]);

            //Czesc Lewa
            if(c > 1)
            {
                T.newNodeL(w, 0);
                T.preindrzewo(T, w.left, tabpre, tabin, poczatek+1, (poczatek+c),inpo);
            }
            else
            {
                if(tabpre[poczatek]==tabin[inpo])
                {
                    T.newNodeR(w, tabin[++inpo]);
                    inpo--;
                }
                else
                    T.newNodeL(w, tabin[inpo]);
            }

            //Czesc Prawa
            if(koniec - poczatek - c - 1 > 0)
            {
                inpo = c+inpo+1;
                T.newNodeR(w, 0);
                T.preindrzewo(T, w.right, tabpre, tabin, poczatek+c+1, koniec, inpo);
            }

            if(poczatek==0)
            {
               // System.out.println("..............");
               // System.out.println("Postorder");
                T.postorder(T.korzen());
                System.out.println();
               // System.out.println("..............");
            }
        }

        public void postindrzewo(Tree T,Node w,int []tabpost, int []tabin, int poczatek, int koniec, int inpo)
        {
            int kr=inpo;
            int c=0;

            if(koniec == tabpost.length-1)// za pierwszym razem
            {
                Node a = new Node(tabpost[koniec],null,null);
                T = new Tree(a);
                w = T.korzen();
            }

            T.insert(tabpost[koniec], w);

            if(koniec-poczatek >= 0)
                while(tabpost[koniec] != tabin[kr+c])
                    c++;

            if(poczatek+c+1 == koniec)
                if(tabpost[poczatek+c+1]==tabin[koniec])
                    T.newNodeR(w, tabin[koniec]);

            //Czesc Lewa
            if(c > 1)
            {

                    T.newNodeL(w, 0);
                    T.postindrzewo(T, w.left, tabpost, tabin, poczatek, (poczatek+c-1),inpo);
            }
            else
            {
                if(tabpost[poczatek]!=tabin[inpo])
                {
                    T.newNodeR(w, tabin[++inpo]);
                    inpo--;
                }
                else
                    T.newNodeL(w, tabin[inpo]);
            }

            //Czesc Prawa
            if(koniec-1 - (poczatek + c) > 0)
            {
                inpo = c+inpo+1;
                    T.newNodeR(w, 0);
                    T.postindrzewo(T, w.right, tabpost, tabin, poczatek+c, koniec-1, inpo);
            }

            if(koniec==tabpost.length-1)
            {
                //System.out.println("Postorder");
                T.preorder(T.korzen());
                System.out.println();
            }
        }

    }

    public static void main(String[] args)
    {

        int ile = input.nextInt();
        String a;
        String b;
            for(int i=0;i<ile;i++)
            {
                Node w = new Node(0,null,null);
                Tree T = new Tree(w);
                int n = input.nextInt();

                a =input.next();
                //System.out.println(a);
                int[] tab = new int[n];
                for(int j=0;j<n;j++)
                    tab[j] = input.nextInt();
                b =input.next();
                //System.out.println(b);
                int[] k = new int[n];
                for(int l=0;l<n;l++)
                    k[l] = input.nextInt();
                if(a.charAt(1)=='O')
                {
                   // System.out.println("Wszedl POST");
                    T.postindrzewo(T, T.korzen(), tab, k, 0, tab.length-1, 0);
                }
                if(a.charAt(1)=='R')
                {
                    //System.out.println("wszedl Pre");
                    T.preindrzewo(T, T.korzen(), tab, k, 0, tab.length-1, 0);
                }


            }


    }
}