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.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;

public class d1 extends PrintWriter {

    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    // static Scanner s=new Scanner(System.in);
    d1 () { super(System.out); }
    public static void main(String[] args) throws IOException{
        d1 d1=new d1();d1.main();d1.flush();
    }
    void main() throws IOException {
        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        StringBuffer sb1 = new StringBuffer();
        PrintWriter out = new PrintWriter(System.out);
       String[] s1 = s();
       int t=i(s1[0]);
      while(t-->0){
          String[] s2=s();
          int n=i(s2[0]);
          int[] ans=new int[n];
          int[] a=new int[n];arr(a,n);int[] b=new int[n];arr(b,n);int[] c=new int[n];arr(c,n);
          int prev=-1;
          for(int i=0;i<n;i++){
              if(a[i]==prev){
                  ans[i]=b[i];prev=b[i];
              }else{
                  ans[i]=a[i];prev=a[i];
              }sb.append(ans[i]+" ");
          }sb.append("\n");
      }
        System.out.println(sb);
    }
    static long powerwithmod(long  x, long y, long p) {
        long  res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
    public void arr(int[] a,int n) throws IOException{
//        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
        String[] s2=s();
        for(int i=0;i<n;i++){
            a[i]=i(s2[i]);
        }
    }
    public void sort(int[] a,int l,int h){
        if(l==h) return;
        int mid=(l+h)/2;

        sort(a,l,mid);
        sort(a,mid+1,h);
        merge(a,l,(l+h)/2,h);
    }
    void merge(int arr[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }


    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static String[] s() throws IOException {
        return s.readLine().trim().split("\\s+");
    }

    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
}
class Student {
    long  a;int b;int c;
    public Student(int a,int b,int c) {
        this.a=a;this.c=c;this.b=b;
    }
}
class Pair {
    int  a,b,c;
    public Pair(int  a,int b,int c){
        this.a=a;this.b=b;this.c=c;}
}
class Sortbyroll implements Comparator<Student> {

    public int compare(Student a, Student b){
        return   a.b-b.b;}
}

