Problem: You are given three sequences: a_1, a_2, …, a_n; b_1, b_2, …, b_n; c_1, c_2, …, c_n.

For each i, a_i ≠ b_i, a_i ≠ c_i, b_i ≠ c_i.

Find a sequence p_1, p_2, …, p_n, that satisfy the following conditions:

  * p_i ∈ \\{a_i, b_i, c_i\}
  * p_i ≠ p_{(i mod n) + 1}.



In other words, for each element, you need to choose one of the three possible values, such that no two adjacent elements (where we consider elements i,i+1 adjacent for i<n and also elements 1 and n) will have equal value.

It can be proved that in the given constraints solution always exists. You don't need to minimize/maximize anything, you need to find any proper sequence.

Input

The first line of input contains one integer t (1 ≤ t ≤ 100): the number of test cases.

The first line of each test case contains one integer n (3 ≤ n ≤ 100): the number of elements in the given sequences.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 100).

The third line contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ 100).

The fourth line contains n integers c_1, c_2, …, c_n (1 ≤ c_i ≤ 100).

It is guaranteed that a_i ≠ b_i, a_i ≠ c_i, b_i ≠ c_i for all i.

Output

For each test case, print n integers: p_1, p_2, …, p_n (p_i ∈ \\{a_i, b_i, c_i\}, p_i ≠ p_{i mod n + 1}).

If there are several solutions, you can print any.

Example

Input


5
3
1 1 1
2 2 2
3 3 3
4
1 2 1 2
2 1 2 1
3 4 3 4
7
1 3 3 1 1 1 1
2 4 4 3 2 2 4
4 2 2 2 4 4 2
3
1 2 1
2 3 3
3 1 2
10
1 1 1 2 2 2 3 3 3 1
2 2 2 3 3 3 1 1 1 2
3 3 3 1 1 1 2 2 2 3


Output


1 2 3
1 2 1 2
1 3 4 3 2 4 2
1 3 2
1 2 3 1 2 3 1 2 3 2

Note

In the first test case p = [1, 2, 3].

It is a correct answer, because:

  * p_1 = 1 = a_1, p_2 = 2 = b_2, p_3 = 3 = c_3 
  * p_1 ≠ p_2 , p_2 ≠ p_3 , p_3 ≠ p_1 



All possible correct answers to this test case are: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].

In the second test case p = [1, 2, 1, 2].

In this sequence p_1 = a_1, p_2 = a_2, p_3 = a_3, p_4 = a_4. Also we can see, that no two adjacent elements of the sequence are equal.

In the third test case p = [1, 3, 4, 3, 2, 4, 2].

In this sequence p_1 = a_1, p_2 = a_2, p_3 = b_3, p_4 = b_4, p_5 = b_5, p_6 = c_6, p_7 = c_7. Also we can see, that no two adjacent elements of the sequence are equal.

Solution (in JAVA):

Solution:
    import java.io.*;
    import java.io.IOException;
    import java.math.BigInteger;
    import java.util.*;



        //import javafx.util.Pair; 
        //import java.util.concurrent.LinkedBlockingDeque;







            
         public class Codeforces {
            
                
                public static long mod = 1000000007 ;
                public static double epsilon=0.00000000008854;//value of epsilon
                public static InputReader sc = new InputReader(System.in);
                public static PrintWriter pw = new PrintWriter(System.out);
                
                public static long pow(long x,long y,long mod){
                    long ans=1;
                    
                    x%=mod;
                    while(y>0){
                        if((y&1)==1){
                            ans=(ans*x)%mod;
                        }
                        y=y>>1;
                        x=(x*x)%mod;
                    }
                    return ans;
                }
                public static ArrayList<ArrayList <Pair>> GetGraph(int n,int m,HashSet<Integer> h){
                    ArrayList<ArrayList <Pair>> a=new ArrayList<>();
                    for(int i=0;i<n;i++){
                        a.add(new ArrayList<>());
                    }
                    for(int i=0;i<m;i++){
                        int u=sc.nextInt()-1;
                        int v=sc.nextInt()-1;
                        if(h.contains(v)){
                            h.remove(v);
                        }
                        a.get(u).add(new Pair(v, 0));
                        //a.get(v).add(new Pair(u, 1));
                    } 
                    return a;
                }
               
                public static int firstNode(int a,int p[]){
                    if(a!=p[a]){
                        p[a]=firstNode(p[a], p);
                    }
                    return p[a];
                }
                public static void Union(int a,int b,int p[]){
                    //int a=firstNode(a1, p);
                    //int b=firstNode(b1, p);
                    /*if(a!=b){
                        if(r[a]<r[b]){
                            p[a]=b;
                        }
                        else if(r[a]>r[b]){
                            p[b]=a;
                        }
                        else{
                            r[b]++;
                            p[a]=b;
                        }
                    }*/
                    if(a!=b)
                    p[firstNode(a,p)]=firstNode(b,p);//if no rank than 
                }
            
               
                public static void main(String[] args) throws Exception {
                    // code starts.
                    int q=sc.nextInt();
                   while(q-->0){
                       int n=sc.nextInt();
                       int a[]=scanArray(n);
                       int b[]=scanArray(n);
                       int c[]=scanArray(n);
                       int ans[]=new int[n];
                       ans[0]=a[0];
                       for(int i=1;i<n-1;i++){
                        if(a[i]!=ans[i-1]){
                            ans[i]=a[i];
                        }
                        else if(b[i]!=ans[i-1]){
                            ans[i]=b[i];
                        }
                        else if(c[i]!=ans[i-1]){
                            ans[i]=c[i];
                        }
                       }
                       if(n>=3){
                        int a1=ans[0];
                        int b1=ans[n-2];
                        if(a[n-1]!=a1&&a[n-1]!=b1){
                            ans[n-1]=a[n-1];
                        }
                        else if(b[n-1]!=a1&&b[n-1]!=b1){
                            ans[n-1]=b[n-1];
                        }
                        else if(c[n-1]!=a1&&c[n-1]!=b1){
                            ans[n-1]=c[n-1];
                        }
                       }
                       for(int i=0;i<n;i++){
                           pw.print(ans[i]+" ");
                       }
                       pw.print("\n");
                    
                   }
                   
                    // Code ends...
                    pw.flush();
                    pw.close();
                }
                public static Comparator<Integer[]> MOquery(int block){
                    return
                    new Comparator<Integer[]>(){
                        @Override
                        public int compare(Integer a[],Integer b[]){
                            int a1=a[0]/block;
                            int b1=b[0]/block;
                            if(a1==b1){
                                if((a1&1)==1)
                                return a[1].compareTo(b[1]);
                                else{
                                    return b[1].compareTo(a[1]);
                                }
                            }
                            return a1-b1;
                        }
                    };
                }
            
                public static Comparator<Long[]> column(int i){
                    return 
                    new Comparator<Long[]>() {
                        @Override
                        public int compare(Long[] o1, Long[] o2) {
                            return o1[i].compareTo(o2[i]);//for ascending
                            //return o2[i].compareTo(o1[i]);//for descending
                        }
                    };
                }
                public static Comparator<Integer[]> column(){
                    return 
                    new Comparator<Integer[]>() {
                        @Override
                        public int compare(Integer[] o1, Integer[] o2) {
                            //return o1[i].compareTo(o2[i]);//for ascending
                            //return o2[i].compareTo(o1[i]);//for descending
                            long a1=o1[0];
                            long a2=o2[1];
                            long b1=o2[0];
                            long b2=o1[1];
                            int ans=0;
                            if(a1*a2>b1*b2){
                                ans=1;
                            }
                            else ans=-1;
                            return ans;
                        }
                    };
                }
                public static Comparator<Integer[]> col(int i){
                    return 
                    new Comparator<Integer[]>() {
                        @Override
                        public int compare(Integer[] o1, Integer[] o2) {
                            if(o1[i]-o2[i]!=0)
                            return o1[i].compareTo(o2[i]);//for ascending
                            return o1[i+1].compareTo(o2[i+1]);
                            //return o2[i].compareTo(o1[i]);//for descending
                        }
                    };
                }
                public static Comparator<Integer> des(){
                    return 
                    new Comparator<Integer>() {
                        @Override
                        public int compare(Integer o1, Integer o2) {
                            //return o1[i].compareTo(o2[i]);//for ascending
                            return o2.compareTo(o1);//for descending
                        }
                    };
                }
                
                
                
                
                public static String reverseString(String s){
                    StringBuilder input1 = new StringBuilder(); 
                    input1.append(s);  
                    input1 = input1.reverse();
                    return input1.toString();
                }
                public static int[] scanArray(int n){
                    int a[]=new int [n];
                    //Random x=new Random();
                    for(int i=0;i<n;i++){
                        a[i]=sc.nextInt();
                    }
                    
            
                    return a;
                }
                public static long[] scanLongArray(int n){
                    long a[]=new long [n];
                    for(int i=0;i<n;i++)
                    a[i]=sc.nextLong();
            
                    return a;
                }
                public static String [] scanStrings(int n){
                    String a[]=new String [n];
                    for(int i=0;i<n;i++)
                    a[i]=sc.nextLine();
            
                    return a;
                }
                public static class InputReader {
            
                    private final InputStream stream;
                    private final byte[] buf = new byte[8192];
                    private int curChar, snumChars;
                    private SpaceCharFilter filter;
            
                    public InputReader(InputStream stream) {
                        this.stream = stream;
                    }
            
                    public int snext() {
                        if (snumChars == -1)
                            throw new InputMismatchException();
                        if (curChar >= snumChars) {
                            curChar = 0;
                            try {
                                snumChars = stream.read(buf);
                            } catch (IOException e) {
                                throw new InputMismatchException();
                            }
                            if (snumChars <= 0)
                                return -1;
                        }
                        return buf[curChar++];
                    }
            
                    public int nextInt() {
                        int c = snext();
                        while (isSpaceChar(c)) {
                            c = snext();
                        }
                        int sgn = 1;
                        if (c == '-') {
                            sgn = -1;
                            c = snext();
                        }
                        int res = 0;
                        do {
                            if (c < '0' || c > '9')
                                throw new InputMismatchException();
                            res *= 10;
                            res += c - '0';
                            c = snext();
                        } while (!isSpaceChar(c));
                        return res * sgn;
                    }
            
                    public long nextLong() {
                        int c = snext();
                        while (isSpaceChar(c)) {
                            c = snext();
                        }
                        int sgn = 1;
                        if (c == '-') {
                            sgn = -1;
                            c = snext();
                        }
                        long res = 0;
                        do {
                            if (c < '0' || c > '9')
                                throw new InputMismatchException();
                            res *= 10;
                            res += c - '0';
                            c = snext();
                        } while (!isSpaceChar(c));
                        return res * sgn;
                    }
            
                    public int[] nextIntArray(int n) {
                        int a[] = new int[n];
                        for (int i = 0; i < n; i++) {
                            a[i] = nextInt();
                        }
                        return a;
                    }
            
                    public String readString() {
                        int c = snext();
                        while (isSpaceChar(c)) {
                            c = snext();
                        }
                        StringBuilder res = new StringBuilder();
                        do {
                            res.appendCodePoint(c);
                            c = snext();
                        } while (!isSpaceChar(c));
                        return res.toString();
                    }
            
                    public String nextLine() {
                        int c = snext();
                        while (isSpaceChar(c))
                            c = snext();
                        StringBuilder res = new StringBuilder();
                        do {
                            res.appendCodePoint(c);
                            c = snext();
                        } while (!isEndOfLine(c));
                        return res.toString();
                    }
            
                    public boolean isSpaceChar(int c) {
                        if (filter != null)
                            return filter.isSpaceChar(c);
                        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
                    }
            
                    private boolean isEndOfLine(int c) {
                        return c == '\n' || c == '\r' || c == -1;
                    }
            
                    public interface SpaceCharFilter {
                        public boolean isSpaceChar(int ch);
                    }
                }
                
            }
            
            class SparseTable{
                int p[][];
                int log[];
                SparseTable(int a[]){
                    log=new int[a.length];
                    for(int i=2;i<a.length;i++){
                        log[i]=log[i/2]+1;
                    }
                    p=new int[a.length][25];
                    
                    for(int i=0;i<a.length;i++){
                        p[i][0]=a[i];
                    }
                    
                    build(p);
                    //System.out.println(Arrays.toString(log));
                }
                void build(int p[][]){
                    for(int h=1;h<25;h++){
                        for(int i=0;i+(1<<(h-1))<p.length;i++){
                            p[i][h]=compare(p[i][h-1], p[i+(1<<(h-1))][h-1]);
                        }
                    }
                }
                int getO1(int l,int r){
                    int k=log[r-l+1];
                    
                        return compare(p[l][k],p[r-(1<<k)+1][k]);
                    
                }
                int compare(int a,int b){
                    return Math.max(a, b);
                }
            }
            class Pair{
                int v,w;
                Pair(int node,int weight){
                    v=node;
                    w=weight;
                }
            }