Grakn Forces 2020 A. Circle Coloring

A. Circle Coloring

Description

You are given three sequences: a1,a2,…,an; b1,b2,…,bn; c1,c2,…,cn.

For each i, ai≠bi, ai≠ci, bi≠ci.

Find a sequence p1,p2,…,pn, that satisfy the following conditions:

• pi∈{ai,bi,ci}
• pi≠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 a1,a2,…,an (1≤ai≤100).

The third line contains n integers b1,b2,…,bn (1≤bi≤100).

The fourth line contains n integers c1,c2,…,cn (1≤ci≤100).

It is guaranteed that ai≠bi, ai≠ci, bi≠ci for all i.

Output

For each test case, print n integers: p1,p2,…,pn (pi∈{ai,bi,ci}, pi≠pimodn+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:

p1=1=a1, p2=2=b2, p3=3=c3

p1≠p2, p2≠p3, p3≠p1

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 p1=a1, p2=a2, p3=a3, p4=a4. 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 p1=a1, p2=a2, p3=b3, p4=b4, p5=b5, p6=c6, p7=c7. Also we can see, that no two adjacent elements of the sequence are equal.

题意： 从给定的a、b、c三个数组中对应的第i个位置选出一个数，记作pi，pi不能与$p_{i+1}$相同，最后输出数组p

c++ AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 7;

int a[maxn][3],p[maxn];

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=0;i<3;i++)
			for(int j=0;j<n;j++)
				scanf("%d",&a[j][i]);	// 将ai、bi、ci放到同一维度
			
		p[0] = a[0][0];
		for(int i=1;i<n;i++)
		{
			int pre = p[i-1],nex = -1;
			if(i == n-1)
				nex = p[0];
			for(int j=0;j<3;j++)
				if(a[i][j] != pre && a[i][j] != nex)
				{
					p[i] = a[i][j];
					break;
				}
		}
		for(int i=0;i<n;i++)
			printf("%d ",p[i]);
		puts("");
	}
	return 0;
}