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.text.DecimalFormat;
import java.util.*;
    public class main2 {
    	static ArrayList<pair> factors;
    	static boolean isComposite[];
    	static ArrayList<Integer> primes;
    	public static boolean isprime(long n){
    		if(n<=10001){
    			return !isComposite[(int)n];
    		}
    		for(int i=0;i<primes.size();i++){
    			if(primes.get(i)*primes.get(i)*1l>n){
    				break;
    			}
    			if(n%primes.get(i)==0){
    				return false;
    			}
    			
    		}
    		return true;
    	}
    	static int[] res;
    	
    	public static void sieve(int n){
    		isComposite=new boolean[n+1];
    		primes =new ArrayList<Integer>();
    		isComposite[0]=true;
    		isComposite[1]=true;
    		for(int i=2;i<=n;i++){
    			if(!isComposite[i]){
    				for(int j=2*i;j<=n;j=j+i){
    					isComposite[j]=true;
    				}
    			}
    			primes.add(i);
    		}
    		
    	}
    	public static void primefactors(long n){
    		 factors=new ArrayList<pair>();
    		for(int x:primes){
    			if(x*x*1l>n){
    				break;
    			}
    		
    			
    			if(n%x==0){
    				
    					pair p=new pair(x,0);
    					 factors.add(p);
    				while(n%x==0){
    				n/=x;
    				p.y++;}
    				
    			}
    		}
    		if(n!=1){
    			factors.add(new pair((int)n,1));
    		}
    		
    	}
    	public static long powfact(long n,long p){
    		int res=0;
    		for(long i=p;i*1l<=n;i=i*p*1l){
    			res+=(n/i);
    		}
    		return res;
    	}
    	
    	public static long GCD(long i, long j){
    	if (i==0){
    		return j;
    	}
    	return GCD(j%i,i);
    	}
    	public static long LCM(long i, long j){
    		return(i*j)/GCD(i,j);
    	}
  
     
    	public static void main(String[] args) throws Exception {
    	Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    	while(t-->0){
    	
int  n=sc.nextInt();
int [] [] freq=new int [n+1][101];
int [] a=new int[n];
int [] b=new int[n];
int [] c=new int[n];
for(int i=0;i<n;i++){
	a[i]=sc.nextInt();
	
	freq[i][a[i]]++;}
for(int i=0;i<n;i++){
	b[i]=sc.nextInt();

	freq[i][b[i]]++;}
for(int i=0;i<n;i++){
	c[i]=sc.nextInt();
	freq[i][c[i]]++;}
	

int [] ans=new int[n];
if(freq[1][a[0]]<3){
	ans[0]=a[0];
}
else if(freq[1][b[0]]<3){
	ans[0]=b[0];
}
else {
	ans[0]=c[0];
}
	for(int i=1;i<n-1;i++){
		
	
		if(freq[i+1][a[i]]<3&&a[i]!=ans[i-1]){
			ans[i]=a[i];
		}
		else if(freq[i+1][b[i]]<3&&b[i]!=ans[i-1]){
			ans[i]=b[i];
		}
		else {
			ans[i]=c[i];
		}
	}
	if(a[n-1]!=ans[0]&&a[n-1]!=ans[n-2]){
		ans[n-1]=a[n-1];
	}
	else if(b[n-1]!=ans[0]&&b[n-1]!=ans[n-2]){
		ans[n-1]=b[n-1];
		
	}
	else {
		ans[n-1]=c[n-1];
	}
	for(int i=0;i<n;i++){
		System.out.print(ans[i]+" ");
		
	}
	System.out.println();
	
	
}

}

	

    	
   
   
     
  
    
    	static class matrix{
    		int a, b,c, d;
    		public matrix(int x,int y, int z,int w){
    			a=x;
    			b=y;
    			c=z;
    			d=w;
    		}
    		
    		public boolean issSem(){
    			return b==c ;
    		}
    	}
    	public static int p(long x){
    		int t=0;
    		while(x>1){
    			t++;
    			x=x/2;
    		}
    		return t;
    	}
     static long[] fact;
     public static long fact(int x){
long y=(int)Math.pow(2,x)-1;
return((y+1)*(y/2)+(y/2+1));
}     
    	
    	
    	static ArrayList<Integer > [] adjlist;
    	static int [] leaves;
    	static PriorityQueue<pair> centroid;
    	
    	public static void dfs1(int u,int p){
    		leaves[u]=1;
    		if(adjlist[u].size()==1&&u!=0){
    			
    			return;
    		}
    		for( int x:adjlist[u]){
    			if(x!=p){
    				dfs1(x,u);
    				leaves[u]+=leaves[x];
    			}
    		}
    	}
    
    	
    	static class pair implements Comparable<pair>{
    		int x;
    		int y;
    		public pair(int x, int y){
    			this.x=x;
    					this.y=y;
    		}
			@Override
			public int compareTo(pair o) {
				// TODO Auto-generated method stub
				return x-o.x;
			}
    	}
    	
    	  	 	static class SegmentTree{
    	   	 		int[] arr , sTree;
    	   	 	static	int N;
    	   	 		public SegmentTree(int[] in){
    	   	 			arr=in;
    	   	 		N=arr.length-1;
    	   	 			sTree=new int[2*N];
    	   	 			
    	   	 			build(1,1,N);
    	   	 		}
    	   	 		public void build(int node, int l, int r){
    	   	 			if(l==r){
    	   	 				sTree[node]=arr[l];
    	   	 			}
    	   	 			else{
    	   	 				int leftchild=node*2;
    	   	 				int rightchild=node*2+1;
    	   	 				int mid =(l+r)/2;
    	   	 				build(leftchild,l,mid);
    	   	 				build(rightchild,mid+1,r);
    	   	 				sTree[node]=Math.min(sTree[leftchild],sTree[rightchild]);
    	   	 			}
    	   	 		}
    	   	 		public  void update(int i, int val){
    	   	 			int node =i+N-1;
    	   	 			arr[i]=val;
    	   	 			sTree[node]=val;
    	   	 			node=node/2;
    	   	 			while(node>0){
    	   	 			int leftchild=node *2;
       	 				int rightchild=node*2+1;
       	 			sTree[node]=sTree[leftchild]&sTree[rightchild];
       	 			node=node/2;
    	   	 			}
    	   	 			return;
    	   	 			
    	   	 		}
    	   	 		public int query(int i, int j){
    	   	 			 return query(1,1, N,  i, j);
    	   	 		}
    	   	 		public int query(int node,int l, int r, int i , int j){
    	   	 			if(i>r||j<l){
    	   	 				return Integer.MAX_VALUE;
    	   	 			}
    	   	 			if(i<=l&&r<=j){
    	   	 				return sTree[node];
    	   	 			}
    	   	 		int leftchild=node*2;
    	 				int rightchild=node*2+1;
    	 				int mid =(l+r)/2;
    	 				
    	 			return	Math.min(query(leftchild,l,mid,i,j),query(rightchild,mid+1,r,i,j));
    	 				
    	   	 		}
    	   	 	}
     
     
    	static class Scanner {
    		StringTokenizer st;
    		BufferedReader br;
     
    		public Scanner(InputStream s) {
    			br = new BufferedReader(new InputStreamReader(s));
    		}
     
    		public boolean hasNext() {
    			// TODO Auto-generated method stub
    			return false;
    		}
     
    		public String next() throws IOException {
    			while (st == null || !st.hasMoreTokens())
    				st = new StringTokenizer(br.readLine());
    			return st.nextToken();
    		}
     
    		public int nextInt() throws IOException {
    			return Integer.parseInt(next());
    		}
     
    		public long nextLong() throws IOException {
    			return Long.parseLong(next());
    		}
     
    		public String nextLine() throws IOException {
    			return br.readLine();
    		}
     
    		public double nextDouble() throws IOException {
    			String x = next();
    			StringBuilder sb = new StringBuilder("0");
    			double res = 0, f = 1;
    			boolean dec = false, neg = false;
    			int start = 0;
    			if (x.charAt(0) == '-') {
    				neg = true;
    				start++;
    			}
    			for (int i = start; i < x.length(); i++)
    				if (x.charAt(i) == '.') {
    					res = Long.parseLong(sb.toString());
    					sb = new StringBuilder("0");
    					dec = true;
    				} else {
    					sb.append(x.charAt(i));
    					if (dec)
    						f *= 10;
    				}
    			res += Long.parseLong(sb.toString()) / f;
    			return res * (neg ? -1 : 1);
    		}
     
    		public boolean ready() throws IOException {
    			return br.ready();
    		}
     
    	}}