Circle Coloring SOLUTIONS GRAKN FORCES 2020

Circle Coloring SOLUTION

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(imodn)+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.

Leave a Comment

close
error: Content is protected !!