E. Perfect Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$3$$$ arrays $$$a, b, c$$$ of size $$$n$$$.

Your task is to construct a permutation $$$p$$$ of size $$$n$$$ to maximize the value of the permutation $$$p$$$.

The value of a permutation $$$p$$$ is defined as $$$\sum_{{p_{i}} \lt i} a_i$$$ + $$$\sum_{{p_{i}} = i} b_i$$$ + $$$\sum_{{p_{i}} \gt i} c_i$$$.

Input

The first line contains one positive integer $$$t$$$ ($$$1 \le t \le 30000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case begins with a line containing one integer $$$n$$$ ($$$1 \le n \le 200000$$$) — the number of elements in each array $$$a, b$$$ and $$$c$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), the array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$), the array $$$b$$$.

The fourth line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$), the array $$$c$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$200000$$$.

Output

For each test case, output a permutation $$$p$$$ you constructed in a single line.

If there are multiple solutions, output any.

Example
Input
3
3
4 4 1
3 3 3
2 4 2
6
9 9 8 2 4 4
3 5 3 9 9 8
2 4 4 8 5 3
10
3 1 4 1 5 9 2 6 5 3
5 8 9 7 9 3 2 3 8 4
6 2 6 4 3 3 8 3 2 7
Output
1 2 3
3 1 2 4 5 6
6 2 3 4 5 1 8 7 9 10
Note

In the first testcase,

  • $$$p_1 = 1 = 1$$$.
  • $$$p_2 = 2 = 2$$$.
  • $$$p_3 = 3 = 3$$$.

Therefore, the value of this permutation is $$$b_1+b_2+b_3 = 3+3+3 = 9$$$, and we can prove this is optimal.

In the second testcase,

  • $$$p_1 = 3 \gt 1$$$.
  • $$$p_2 = 1 \lt 2$$$.
  • $$$p_3 = 2 \lt 3$$$.
  • $$$p_4 = 4 = 4$$$.
  • $$$p_5 = 5 = 5$$$.
  • $$$p_6 = 6 = 6$$$.

Therefore, the value of this permutation is $$$c_1+a_2+a_3+b_4+b_5+b_6 = 2+9+8+9+9+8 = 45$$$, and we can prove this is optimal.