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.
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using lli = long long int;
using ld = long double;
using ull = unsigned long long int;

#define FOR(i,x,n) for(lli i=x;i<n;i++)
#define RFOR(i,x,n) for(lli i=x;i>=n;i--)
#define FORN(i,x,n,a) for(lli i=x;i<n;i=i+a)
#define RFORN(i,x,n,a) for(lli i=x;i>=n;i=i-a)
#define pb push_back
#define Resize(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unique_sort(c) (sort(c.begin(),c.end()), Resize(c))
#define mem(x,y) memset(x,y,sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (lli)x.size()
#define fs first
#define ss second
#define mp make_pair
#define gt(i,t) get<i>(t)
#define lb '\n'
#define il inline void
#define debug(x) cerr<<#x<<" = "<<(x)<<endl;
#define rd read
#define pr print

const lli mod=1e9+7;

#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#define fwrite_unlocked fwrite
#define fflush_unlocked fflush
#endif

template <typename T, typename U, typename V> using TP = tuple<T,U,V>;
template <typename T> using VI = vector<T>;
template <typename T> using LI = list<T>;
template <typename T, typename U> using PI = pair<T,U>;
template <typename T, typename U> using VPI = vector<pair<T,U>>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using PQS = priority_queue<T, VI<T>, greater<T>>;

static int gc() { return getchar_unlocked(); }

static char next_char() { char c = gc(); return c;}
static void read(char& v) { while (isspace(v = gc())) ;}
static void read(bool& v) { v = next_char() != '0'; }
static void read(string& v) {v.clear(); for (char c = next_char(); !isspace(c); c = gc()) v += c; }
	
static void read(int& v) {
	v = 0;
	bool neg = false;
	char c = next_char();
	if (c == '-') { neg = true; c = gc(); }
	for (; isdigit(c); c = gc()) v = v * 10 + (c - '0');
	if (neg) v = -v;
}

static void read(lli& v) {
	v = 0;
	bool neg = false;
	char c = next_char();
	if (c == '-') { neg = true; c = gc(); }
	for (; isdigit(c); c = gc()) v = v * 10 + (c - '0');
	if (neg) v = -v;
}
	
static void read(ld& v) {
	v = 0;
	ld dp = 1;
	bool neg = false, after_dp = false;
	char c = next_char();
	if (c == '-') { neg = true; c = gc();}
	for (; isdigit(c) || c == '.'; c = gc()) {
			if (c == '.') after_dp = true;
			else if (after_dp) v += (c - '0') * (dp *= 0.1);
			else v = v * 10 + (c - '0');
	}
	if (neg) v = -v;
}

static string read_line(){
		string v;
		for (char c = gc(); c != '\n' && c != '\0'; c = gc()) v += c;
		return v;
	}

template <size_t N = 0, class T> static void read_tuple_impl(T& v) {
    if constexpr (N < tuple_size_v<T>) { read(gt(N,v)); read_tuple_impl<N + 1>(v); } 
}

template <class T, class U> static void read(PI<T, U>& v) { read(v.fs); read(v.ss); }
template <class T> static void read(VI<T>& v) { for (auto& e : v) read(e); }
template <class T, class U, class V> static void read(TP<T, U, V>& v) { read_tuple_impl(v); }

template <typename T, typename... Args> static void read(T& r, Args&... args) { read(r); read(args...); }

template <typename T1, typename T2> inline void chkmin(T1 &a, const T2 & b) {if (a > b) a = b;}
template <typename T1, typename T2> inline void chkmax(T1 &a, const T2 & b) {if (a < b) a = b;}


struct BoolStr {
	const char *t, *f;
	BoolStr(const char* _t, const char* _f) : t(_t), f(_f) {}
} Yes("Yes", "No"), yes("yes", "no"), YES("YES", "NO"), Int("1", "0");

struct DivStr {
	const char *d, *l;
	DivStr(const char* _d, const char* _l) : d(_d), l(_l) {}
} spc(" ", "\n"), no_spc("", "\n"), end_line("\n", "\n"), comma(",", "\n"), no_endl(" ", "");


static void print(int v){
		char buf[12]{};
		if (auto [ptr, e] = to_chars(begin(buf), end(buf), v); e == errc{})fwrite(buf, sizeof(char), ptr - buf, stdout);
        else assert(false);
}

static void print(lli v){
	char buf[21]{};
	if (auto [ptr, e] = to_chars(begin(buf), end(buf), v); e == errc{}) fwrite(buf, sizeof(char), ptr - buf, stdout);
    else assert(false);
}

BoolStr B{Yes};
DivStr D{spc};

template <class T> void print(const T& v) {cout << v; }

static void print(bool v) {print(v ? B.t : B.f);}
static void print(vector<bool>::reference v) { print(v ? B.t : B.f); }
static void print(char v) { putchar_unlocked(v); }
static void print(const char* v) {fwrite_unlocked(v, 1, strlen(v), stdout); }
static void print(double v) { printf("%.20f", v); }
static void print(long double v) { printf("%.20Lf", v); }

template <class T, class U> void print(const PI<T, U>& v){ print(v.fs); print(D.d); print(v.ss);}
	
template <class InputIterater> void print_range(const InputIterater& begin, const InputIterater& end) {
	for (InputIterater i = begin; i != end; ++i) { if (i != begin) print(D.d); print(*i); }
}

template <class T> void print(const VI<T>& v) { print_range(all(v)); }
template <class T, size_t N> void print(const array<T, N>& v) { print_range(all(v)); }

template <class T> void print(const VI<VI<T>>& v) { 
    for (size_t i = 0; i < v.size(); ++i) {if(i) print(D.l); print(v[i]); }
}

template <typename T, typename... Args> static void print(T r, Args... args) { print(r); print(args...); }


void solve()
{
    lli n; rd(n);
    VI<VI<lli>> v(3, VI<lli>(n));
    rd(v);
    
    VI<lli> ans(n);
    FORN(i,0,n-1,2){ans[i] = v[0][0]; ans[i+1] = v[1][0];} if(n&1)ans[n-1] = v[2][0];
    pr(ans, lb);
}

int main() 
{
    fast();
    lli t; read(t);
    while(t--)
    {
        solve();
    }
    return 0;
}