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.
#include<bits/stdc++.h>
#include<sstream>
#pragma GCC optimize ("-O3")
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sortv(a) sort(a.begin(),a.end())
#define ll long long
#define ld long double
#define int long long
#define double long double
#define pb push_back
#define max(a,b) (a>b?a:b-a)
#define min(a,b) (a<b?a:b)
#define diff(a,b) (a>b?a-b:b-a)
#define fr(n) for(int i=0;i<n;i++)
#define forn(i,n) for(int i=0;i<n;i++)
#define yes(x) if(x == 1)cout << "YES" << endl;else cout << "NO" << endl;
const int N=1e6+5;
const int MAX=1e7+9;
double PI  = 3.14159265;

int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
  
        // If the element is present at the middle 
        // itself 
        if (arr[mid] == x) 
            return mid; 
  
        // If element is smaller than mid, then 
        // it can only be present in left subarray 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
  
        // Else the element can only be present 
        // in right subarray 
        return binarySearch(arr, mid + 1, r, x); 
    } 
  
    // We reach here when element is not 
    // present in array 
    return -1; 
} 

void pairsort(int a[], int b[], int n){
    pair<int, int> pairt[n];
    for (int i = 0; i < n; i++) 
    {
        pairt[i].first = a[i];
        pairt[i].second = b[i];
    }
    sort(pairt, pairt + n);
    for (int i = 0; i < n; i++) 
    {
        a[i] = pairt[i].first;
        b[i] = pairt[i].second;
    }
}

int gcd(int a, int b){
    if (b == 0)
        return a;
    return gcd(b, a % b); 
}

int isprime(int n){
    if(n < 2)
        return 0;
    if(n < 4)
        return 1;
    if(n % 2 == 0 or n % 3 == 0)
        return 0;
    for(int i = 5; i*i <= n; i += 6)
        if(n % i == 0 or n % (i+2) == 0)
            return 0;
    return 1;
}

long long C(int n, int r) {
    if(r>n-r) 
        r=n-r;
    long long ans=1;
    for(int i=1;i<=r;i++){
        ans*=n-r+i;
        ans/=i;
    }
    return ans;
}

int mod = 1e9+7;
int modexpo(int x,int p){
    int res = 1;
    x = x%mod;
    while(p){
        if(p%2)
            res = res * x;
        p >>= 1;
        x = x*x % mod;
        res %= mod;
    }      
    return res;
}

int countDistinct(int arr[], int n) 
{ 
    // First sort the array so that all 
    // occurrences become consecutive 
    sort(arr, arr + n); 
  
    // Traverse the sorted array 
    int res = 0; 
    for (int i = 0; i < n; i++) { 
  
        // Move the index ahead while 
        // there are duplicates 
        while (i < n - 1 && arr[i] == arr[i + 1]) 
            i++; 
  
        res++; 
    } 
  
    return res; 
}

int bin2int(string s){
    reverse(s.begin(),s.end());
    int b=1;
    int x=0;
    for (int i = 0; i < s.length(); ++i){
        if(s[i]=='1')
            x+=b;
        b*=2;
    }
    return x;
}

int getSum(int n) 
 { 
    int sum; 
  
    /* Single line that calculates sum */
    for (sum = 0; n > 0; sum += n % 10, n /= 10); 
  
    return sum; 
 }

vector<int>adj[N];
vector<int>cost;
int src,des,w,u,v;
map<int,int>dist,res,parent,vis;
int n,k;
int p=1;
void dfs(int x)
{
    vis[x]=1;
    for(int i=0;i<adj[x].size();i++)
    {
        if(!vis[adj[x][i]])
        {
            dist[adj[x][i]]=dist[x]+1;
            parent[adj[x][i]]=x;
            dfs(adj[x][i]);
        }
    }
}

void bfs()
{
    int s=1;
    queue<int>q;
    q.push(s);
    parent[s]=1;
    vis[s]=1;
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        for(int i=0;i<adj[s].size();i++)
        {
            if(!vis[adj[s][i]])
            {
                q.push(adj[s][i]);
                vis[adj[s][i]]=1;
                parent[adj[s][i]]=s;
            }
        }
    }
}


string intToString(int n){
    string s ="";
    while(n>0){
        s+=char(n%10+'0');
        n/=10;
    }
    reverse(s.begin(), s.end());
    return s;
}

int lcm(int n,int m){
    return (n*m)/__gcd(n,m);        
}

std::vector<int> primes; 
void SieveOfEratosthenes(int n) 
{ 
    
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
    
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.pb(p); 

} 

int solve()
{













int n;
cin >> n;

// vector<vector<int>> v;
int a[3];
    cin >> a[1] >> a[2] >> a[0];
int x = a[0];

vector<int> ret;
ret.pb(x);
fr(n-1)
{

    cin >> a[1] >> a[2] >> a[0];
    if(a[1] != x)
        ret.pb(a[1]),x=a[1];
    else
        ret.pb(a[0]),x=a[0];   
}

for(auto x: ret)
{
    cout << x << " ";
}





















 



cout << endl;
return 0;
}

int32_t main()
{ 
IOS  
int q = 1;
cin>>q;

for(int i=1;i<=q;i++){

solve();
}
}
 





