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.util.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.io.*;
import java.lang.Math.*;
 public class KickStart2020{
	static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
        float nextFloat() {
        	return Float.parseFloat(next());
        }
 
        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }}	
	static boolean equal(String a) {
		boolean hachu = true;
		char ab = 'a';
		for(int i = 0; i < a.length(); i++) {
			if(ab != a.charAt(i)) {
				hachu = false;
				break;
			}
		}
		return hachu;
	}
	static boolean compare(String a) {
		int z = 0;
		for(int i = 0; i < a.length(); i++) {
			if(a.charAt(i) == '1') {
				z = i;
				break;
			}
		}
		String c = a.substring(0, z + 1);
		String d = a.substring(z + 1, a.length());
		if(equal(c) && equal(d)) return true;
		else return false;
	}
	static boolean isPalindrome(String a, int b) {
		boolean z = true;
		for(int i = 0; i < b; i++) {
			if(a.charAt(i) != a.charAt(a.length() - 1 - i)) {
				z = false;
				break;
			}
		}
		return z;
	}
	static int zeroes(String s) {
		int x = 0;
		int y = 0;
        for(int i = 0; i < s.length(); i++) {
        	if(s.charAt(i) == '1') {
        		x = i;
        		break;
        	}
        }
        for(int i = s.length() - 1; i >= 0; i--) {
        	if(s.charAt(i) == '1') {
        		y = i;
        		break;
        	}
        }
        int sum = 0;
        if(x < y - 1) {
        	for(int i = x + 1; i <= y - 1; i++) {
        		if(s.charAt(i) == '0')sum++;
        	}
        }
        return sum;
	}
	static int[] tree(int l, int r, int k, int arr[], int brr[]) {
		if(l > r) {
			return brr; 
		}
		else {
			int max = -1;
			int pos = 0;
			for(int i = l; i <= r; i++) {
				if(max < arr[i]) {
					max = arr[i];
					pos = i;
				}
			}
			k++;
			brr[pos] = k;
			brr = tree(l, pos - 1, k, arr, brr);
			brr = tree(pos + 1, r, k, arr, brr);
			return brr;
		}
	}
	static int returner (String a, String b) {
		int i = a.length() - 1;
		int count = 0;
		for(; i >= 0; i--) {
			if(a.charAt(i) != b.charAt(i)) {
				break;
			}
		}
		return i;
	}
	static boolean isAscending(char arr[]) {
		boolean hachu = true;
		boolean hachu1 = true;
		for(int i = 0; i < arr.length; i++) {
			if(arr[i] == '2') continue;
			if(arr[i] == '1') {
				hachu = false;
			}
			if(arr[i] == '0' && !hachu) {
				hachu1 = false;
				break;
			}
		}
		return hachu1;
	}
		public static void main(String[] args) throws Exception{
FastReader sc = new FastReader();
int t = sc.nextInt();
while(t-- > 0) {
	  int n = sc.nextInt();
	  int arr[] = new int[n];
	  int brr[] = new int[n];
	  int crr[] = new int[n];
	  int drr[] = new int[n];
	  for(int i = 0; i < n; i++)arr[i] = sc.nextInt();
	  for(int i = 0; i < n; i++)brr[i] = sc.nextInt();
	  for(int i = 0; i < n; i++)crr[i] = sc.nextInt();
	  drr[0] = arr[0];
	  for(int i = 1; i < n; i++) {
		  if(i == n - 1) {
			  if(arr[i] != drr[i - 1] && arr[i] != drr[0]) drr[i] = arr[i];
			  else if(brr[i] != drr[i - 1] && brr[i] != drr[0]) drr[i] = brr[i];
			  else drr[i] = crr[i];
			  continue;
		  }
		 if(arr[i] != drr[i - 1]) {
			 drr[i] = arr[i];
		 }
		 else drr[i] = brr[i];
		                }
	  for(int e: drr) System.out.print(e + " ");
	  System.out.println();
  }
}
 }