N. Stable Factory Assignment
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Khaled is the CEO of a rapidly growing industrial empire. His company recently acquired $$$N$$$ new factories, and he has hired $$$N$$$ workers to operate them. Both the workers' homes and the factories are located along a long, straight highway, which can be represented as the $$$X$$$-axis.

The $$$i$$$-th worker lives at coordinate $$$x_i$$$, and the $$$j$$$-th factory is located at coordinate $$$y_j$$$. Khaled needs to assign exactly one worker to each factory so that no two workers are assigned to the same factory.

Khaled requires a "stable" assignment. An assignment is invalid if swapping two workers' factories strictly increases the sum of their squared travel distances. Formally, for any worker $$$i$$$ assigned to factory $$$a$$$ and worker $$$j$$$ assigned to factory $$$b$$$, the following condition must NOT hold:

$$$$$$(x_i - y_a)^2 + (x_j - y_b)^2 \lt (x_i - y_b)^2 + (x_j - y_a)^2$$$$$$

Given the locations, help Khaled find any valid assignment satisfying his strict stability condition.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 3000$$$) — the number of workers and the number of factories.

The second line of each test case contains $$$N$$$ distinct integers $$$x_1, x_2, \dots, x_N$$$ ($$$-10^9 \le x_i \le 10^9$$$) — the coordinates of the workers.

The third line of each test case contains $$$N$$$ distinct integers $$$y_1, y_2, \dots, y_N$$$ ($$$-10^9 \le y_i \le 10^9$$$) — the coordinates of the factories.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$3000$$$.

Output

For each test case, output a single line containing $$$N$$$ space-separated integers $$$p_1, p_2, \dots, p_N$$$, where $$$p_i$$$ is the 1-based index of the factory assigned to the $$$i$$$-th worker.

If there are multiple valid assignments that satisfy Khaled's condition, you may output any of them.

Example
Input
1
4
7 -5 -9 5
2 -8 7 -11
Output
4 1 3 2