Santa Claus

On Christmas Eve, Santa takes gifts from the elves and gives them to children, bringing joy to their hearts.

The city has $N$ houses along a road, numbered from 1 to $N$ ($1 ≤ N ≤ 96 226$). House $i$ has the following data:

• $X_i$ ($0 ≤ X_1 ≤ X_2 ≤ ... ≤ X_N ≤ 1 000 000 000$): the position of house $i$ on the road
• $H_i$ ($0 ≤ H_i ≤ 1$)
• $V_i$ ($0 ≤ V_i ≤ N$)

If $H_i = 0$, house $i$ has an elf holding one gift of value $V_i$. If $H_i = 1$, house $i$ has a child waiting for one gift of minimum value $V_i$.

There are $N$ scenarios. In scenario $i$, Santa enters the city at coordinate 0 with an empty gift bag. He first walks right to house $i$ at coordinate $X_i$, then walks left to some position $X_{L_i} ≤ X_i$. Each time he passes an elf's house he has not visited before, he takes that gift and puts it in the bag. Each time he passes a child's house that has not yet received a gift, he can (but does not have to) pick one gift from the bag and hand it to the child. The chosen gift must have a value at least as large as $V$, the child's minimum, and it is removed from the bag.

In scenario $i$, Santa travels the distance $D_i = 2X_i - X_{L_i}$. For each scenario, find the minimum distance $D_i$ Santa must travel to give out all the elves' gifts. Some children may receive no gift, but all gifts must be distributed and no child may receive more than one. If no such $D_i$ exists, set $D_i = -1$. In particular, if Santa cannot reach all the elves' houses, the answer for that scenario is always $-1$.

The first line contains one integer $T$ ($1 ≤ T ≤ 10$), the number of tests. Each test consists of four lines:

• Line 1: the number of houses $N$
• Line 2: $X_1, X_2, ..., X_N$
• Line 3: $H_1, H_2, ..., H_N$
• Line 4: $V_1, V_2, ..., V_N$

The sum of $N$ over all tests does not exceed 500 000.

For each test, output a single line with $N$ integers $D_1, D_2, ..., D_N$.

In the first test of the first input, there are 8 houses. Houses 2, 3 and 4 each hold an elf with a gift of value 2, 3 and 3 respectively. House 5 holds a child who wants a gift of value 5. No elf has a gift that large, so that child receives nothing.

In scenarios 1, 2 and 3, Santa does not visit all the elves, so $D_1 = D_2 = D_3 = -1$.

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

In scenario 7, Santa must return to the first house ($X_{L_7} = 10$) to give out all 3 gifts, so $D_7 = 40$.

In scenario 8, Santa does not need to return at all ($X_{L_8} = X_8 = 40$) to give out all 3 gifts, so $D_8 = 35$.