27403번 - 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 (1 ≤ N ≤ 96 226) houses along the road, numbered from 1 to N. For each house i we are given the following information:

• X_i (0 ≤ X₁ ≤ X₂ ≤ ... ≤ X_N ≤ 1 000 000 000);
• H_i (0 ≤ H_i ≤ 1);
• V_i (0 ≤ V_i ≤ N).

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.

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.

The first line of input contains one integer T (1 ≤ T ≤ 10) - 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₁, X₂, ..., X_N.

The third line contains N integers: H₁, H₂, ..., H_N.

The fourth line contains the N integers: V₁, V₂, ..., V_N.

The sum of the N values over all the T tests does not exceed 500 000.

For each of the T tests output a single line containing N integers: D₁, D₂, ..., D_N.

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₁ = D₂ = D₃ = -1.

In scenarios 4, 5 and 6, Santa does not visit enough children that would accept his 3 gifts, thus D₄ = D₅ = D₆ = -1.

In scenario 7, Santa needs to return to the first house (XLeft₇ = 10) to distribute all the 3 gifts, thus D₇ = 40.

In scenario 8, Santa does not need to return at all (XLeft₈ = X₈ = 40) to distribute all the 3 gifts, thus D₈ = 35.