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 javafx.print.Collation;

import javax.net.ssl.SSLEngineResult;
import java.io.*;
import java.math.BigInteger;
import java.text.CollationElementIterator;
import java.util.*;
import java.lang.*;
import java.util.Comparator;

public class ai {
    InputStream is;
    PrintWriter out;
    long mod = (long)(1e9 + 7), inf = (long)(3e18);
    int cnt[];
    void solve() throws Exception {
//        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new
//                FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);
//        out.flush();
        int t = ni();
        while(t-->0){
            int n = ni();
            int arr[] = new int[n];
            int brr[] = new int[n];
            int crr[] = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = ni();
            }
            for(int i=0;i<n;i++){
                brr[i] = ni();
            }
            for(int i=0;i<n;i++){
                crr[i] = ni();
            }
            int ans[] = new int[n];
            int curr = -1;
            for(int i=0;i<n;i++){
                if(curr==-1){
                    ans[i] = arr[i];
                    curr = arr[i];
                }
                else{
                    if(arr[i] != curr){
                        ans[i] = arr[i];
                        curr = arr[i];
                    }
                    else if(brr[i] != curr){
                        ans[i] = brr[i];
                        curr = brr[i];
                    }
                    else if(crr[i] != curr){
                        ans[i] = crr[i];
                        curr = crr[i];
                    }
                }
            }
            for(int i:ans){
//                System.out.print(i+" ");
            }

            if(ans[0] == ans[n-1]){
                if(brr[0] != ans[n-1] && brr[0] != ans[1]){
                    ans[0] = brr[0];
                }
                else{
                    ans[0] = crr[0];
                }
            }
            for(int i:ans){
                System.out.print(i+" ");
            }
            System.out.println();

        }
    }
    public long gcd(long a,long b){
        if(a%b==0)return b;
        return gcd(b,a%b);
    }
    public int gcd(int a,int b){
        if(a%b==0)return b;
        return gcd(b,a%b);
    }

    public long pow(long a,long b,int c){
        if(b==1)return a%c;
        long x = pow(a,b/2,c);
        if(b%2==0){
            return (x*x)%c;
        }
        else{
            return (((x*x)%c)*a)%c;
        }
    }
    public void test(String x){
        x += "A";
        System.out.println(x);
    }
    public void build(long arr[],long brr[],int a[],int n,int l,int r){
        if(l==r){
            arr[n] = brr[n] = a[l];
        }
        else{
            int mid = (l+r)/2;
            build(arr,brr,a,2*n,l,mid);
            build(arr,brr,a,2*n+1,mid+1,r);
            arr[n] = arr[2*n] + arr[2*n+1];
            brr[n] = Math.max(brr[2*n],brr[2*n+1]);
        }
    }
    public long sum(long arr[],int l,int r,int n,int start,int end){
        if(start>end)return 0;
        if(l==start && r==end){
            return arr[n];
        }
        int mid = (l+r)/2;
        return sum(arr,l,mid,2*n,start,Math.min(end,mid)) + sum(arr,mid+1,r,2*n+1,Math.max(mid+1,start),end);
    }
    public void increment(long arr[],long brr[],int n,int l,int r,int tl,int tr,HashMap<Long,Integer> map){
        if(l>r)return;
        if(l==r && tl==tr){
            arr[n] = map.get(arr[n]);
            brr[n] = map.get(brr[n]);
        }
        else{
            int mid = (tl+tr)/2;
            if(brr[2*n]>2)
            increment(arr,brr,2*n,l,Math.min(r,mid),tl,mid,map);
            if(brr[2*n+1]>2)
            increment(arr,brr,2*n+1,Math.max(l,mid+1),r,mid+1,tr,map);
            arr[n] = arr[2*n] + arr[2*n+1];
            brr[n] = Math.max(brr[2*n],brr[2*n+1]);
        }
    }
    public int[] sieve(int n){
        int []ans = new int[n];
        ans[1]=1;
        int i=2;
        while(i<n){
            if(ans[i]==0){
                int j=2*i;
                while(j<n){
                    if(ans[j]==0)
                        ans[j] = i;
                    j+=i;
                }
            }
            i++;
        }
        return ans;
    }
    public static void main(String[] args)throws Exception { new ai().run(); }
    void run() throws Exception {
//        is = new FileInputStream("C:\\Users\\compute\\Desktop\\input.txt");
        is = System.in;
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }

    byte input[] = new byte[1024];
    int len = 0, ptr = 0;

    int readByte() {
        if(ptr >= len) { ptr = 0;
            try { len = is.read(input); }
            catch(IOException e) { throw new InputMismatchException(); }
            if(len <= 0) { return -1; }
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { return !( c >= 33 && c <= 126 ); }
    int skip() {
        int b = readByte();
        while(b != -1 && isSpaceChar(b)) { b = readByte(); }
        return b;
    }

    char nc() { return (char)skip(); }
    String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); }
        return sb.toString();
    }
    String nLine() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while( !(isSpaceChar(b) && b != ' ') ) { sb.appendCodePoint(b); b = readByte(); }
        return sb.toString();
    }
    int ni() {
        int n = 0, b = readByte();
        boolean minus = false;
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); }
        if(b == '-') { minus = true; b = readByte(); }
        if(b == -1) { return -1; }  //no input
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); }
        return minus ? -n : n;
    }
    long nl() {
        long n = 0L;    int b = readByte();
        boolean minus = false;
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); }
        if(b == '-') { minus = true; b = readByte(); }
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); }
        return minus ? -n : n;
    }

    double nd() { return Double.parseDouble(ns()); }
    float nf() { return Float.parseFloat(ns()); }
    int[] na(int n) {
        int a[] = new int[n];
        for(int i = 0; i < n; i++) { a[i] = ni(); }
        return a;
    }
    char[] ns(int n) {
        char c[] = new char[n];
        int i, b = skip();
        for(i = 0; i < n; i++) {
            if(isSpaceChar(b)) { break; }
            c[i] = (char)b; b = readByte();
        } return i == n ? c : Arrays.copyOf(c,i);
    }
}