Santa Claus

It's a well known fact that in the Christmas Eve it's Santa's job to take the gifts from the elves and give them to children, bringing joy and happiness to their hearts.

In The City there are $N$ houses along the road, numbered from $1$ to $N$. For each house $i$ we are given the following information: $X_i, H_i, V_i$.

$X_i$ is the position of the $i$-th house along the road. If $H_i = 0$, then in the $i$-th house there is an elf with a single gift of value $V_i$. If $H_i = 1$, then in the $i$-th house there is a single child waiting for a single gift of minimum value $V_i$.

Task

There will be $N$ scenarios. In the $i$-th scenario Santa enters the city at coordinate $0$, carrying an empty gift bag. He first moves to the right until he reaches the $i$ -th house (which is located at coordinate $X_i$) and then he moves to the left until he reaches some other position $XLeft_i ≤ X_i$. Whenever Santa passes by an elf's house which he hasn't visited before, he takes their gift and puts it into the bag. Whenever Santa passes by a child's house which hasn't already received a gift, he can (but doesn't have to!) pick one of the gifts currently in the bag and hand it to the child, removing it from the bag. This can only be accomplished if the value of the chosen gift is at least as large as the minimum value $V$ specified by the child.

In the $i$-th scenario, Santa travels distance $D_i = 2X_i - XLeft_i$. For each scenario it's your job to find the minimum distance $D_i$ Santa has to travel to distribute all the elves' gifts to children. Note that it may be the case that some children don't receive any gift - this is acceptable as long as all the gifts are distributed and no child receives more than one gift. If no such $D_i$ exists, take $D_i = -1$. In particular, note that this will always be the case for scenarios where Santa can't reach all the elves' houses.

Input data

The first line of input contains one integer $T$ - the number of tests to solve.

The description of $T$ tests follows. Each test consists of four lines:

The first line contains one integer $N$ - the number of houses in the city.

The second line contains $N$ integers: $X_1, X_2, \dots, X_N$.

The third line contains $N$ integers: $H_1, H_2, \dots, H_N$.

The fourth line contains the $N$ integers: $V_1, V_2, \dots, V_N$.

Output data

For each of the $T$ tests output a single line containing $N$ integers: $D_1, D_2, \dots, D_N$.

Constraints and clarifications

• $1 \leq N \leq 96 \ 068$
• $1 \leq T \leq 10$
• $0 \leq X_1 \leq X_2 \leq \dots \leq X_N \leq 1 \ 000 \ 000$
• $0 \leq H_i \leq 1$
• $0 \leq V_i \leq N$
• The sum of the $N$ values over all the $T$ tests does not exceed $500 \ 000$.

Example 1

stdin

2
8
10 11 12 13 14 16 25 35
1 0 0 0 1 1 1 1
2 2 3 3 5 1 1 1
16
10 11 12 13 14 15 16 17 18 19 20 23 24 31 33 37
1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1
2 1 7 3 1 10 10 6 5 5 1 6 1 10 8 2

stdout

-1 -1 -1 -1 -1 -1 40 35
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 36 24 31 33 37

Explanation

In the first test of the first input sample there are $8$ houses.

Inside houses $2, 3$ and $4$ there are $3$ elves with presents of values $2, 3$ and $3$ respectively.

Inside the $5$-th house there is a child expecting a present of value $5$. Since Santa can't get such a present from any of the elves, that child will receive no gift.

In scenarios $1, 2$ and $3$, Santa doesn't visit all the elves, thus $D_1 = D_2 = D_3 = -1$.

In scenarios $4, 5$ and $6$, Santa does not visit enough children that would accept his $3$ gifts, thus $D_4 = D_5 = D_6 = -1$.

In scenario $7$, Santa needs to return to the first house $(XLeft_7 = 10)$ to distribute all the $3$ gifts, thus $D_7 = 40$.

In scenario $8$ , Santa does not need to return at all $(XLeft_8 = X_8 = 40)$ to distribute all the $3$ gifts, thus $D_8 = 35$.

Example 2

stdin

2
9
1 2 3 4 15 16 17 18 19
0 0 1 1 1 0 0 1 1
5 7 4 1 2 3 1 6 2
9
1 2 3 4 15 16 17 18 19
0 0 1 1 1 0 0 1 1
5 7 4 1 2 3 1 6 1

stdout

-1 -1 -1 -1 -1 -1 -1 32 34
-1 -1 -1 -1 -1 -1 -1 32 23