산타 클로스

크리스마스 이브에 산타는 요정에게 선물을 받아 아이들에게 전합니다.

도시에는 길을 따라 $N$개의 집이 있고, 1번부터 $N$번까지 번호가 붙어 있습니다 ($1 ≤ N ≤ 96 226$). 집 $i$마다 다음 정보가 주어집니다.

• $X_i$ ($0 ≤ X_1 ≤ X_2 ≤ ... ≤ X_N ≤ 1 000 000 000$): 도로에서 집 $i$의 위치
• $H_i$ ($0 ≤ H_i ≤ 1$)
• $V_i$ ($0 ≤ V_i ≤ N$)

$H_i = 0$이면 집 $i$에는 값이 $V_i$인 선물 하나를 가진 요정이 있습니다. $H_i = 1$이면 집 $i$에는 최소 값 $V_i$인 선물 하나를 기다리는 아이가 있습니다.

시나리오는 $N$개입니다. 시나리오 $i$에서 산타는 좌표 0에서 빈 선물 가방을 들고 도시에 들어섭니다. 먼저 오른쪽으로 이동해 좌표 $X_i$의 집 $i$에 도착한 뒤, 왼쪽으로 이동해 $X_{L_i} ≤ X_i$인 위치까지 갑니다. 아직 방문하지 않은 요정의 집을 지날 때마다 그 선물을 가방에 넣습니다. 아직 선물을 받지 못한 아이의 집을 지날 때는 가방에 있는 선물 중 하나를 골라 아이에게 줄 수 있습니다 (반드시 줄 필요는 없습니다). 고른 선물의 값은 아이가 요구한 최소 값 $V$ 이상이어야 하며, 준 선물은 가방에서 빠집니다.

시나리오 $i$에서 산타가 이동하는 거리는 $D_i = 2X_i - X_{L_i}$입니다. 각 시나리오마다 모든 요정의 선물을 나눠 줄 수 있는 최소 이동 거리 $D_i$를 구하세요. 선물을 받지 못하는 아이가 있어도 되지만, 모든 선물을 나눠 주어야 하며 한 아이가 두 개 이상 받아서는 안 됩니다. 그런 $D_i$가 없으면 $D_i = -1$로 둡니다. 특히 산타가 모든 요정의 집에 갈 수 없는 시나리오의 답은 항상 $-1$입니다.

첫 줄에 테스트 개수 $T$ ($1 ≤ T ≤ 10$)가 주어집니다. 각 테스트는 다음 네 줄로 이루어집니다.

• 1번째 줄: 집의 수 $N$
• 2번째 줄: $X_1, X_2, ..., X_N$
• 3번째 줄: $H_1, H_2, ..., H_N$
• 4번째 줄: $V_1, V_2, ..., V_N$

모든 테스트의 $N$을 더한 값은 500 000을 넘지 않습니다.

각 테스트마다 $N$개의 정수 $D_1, D_2, ..., D_N$을 공백으로 구분해 한 줄에 출력합니다.

첫 번째 입력의 첫 번째 테스트에는 집이 8개 있습니다. 집 2, 3, 4에는 각각 값이 2, 3, 3인 선물을 가진 요정이 있습니다. 집 5에는 값이 5인 선물을 원하는 아이가 있습니다. 그만큼 큰 선물을 가진 요정이 없으므로 이 아이는 선물을 받지 못합니다.

시나리오 1, 2, 3에서 산타는 모든 요정을 방문하지 않으므로 $D_1 = D_2 = D_3 = -1$입니다.

시나리오 4, 5, 6에서 산타는 3개의 선물을 받을 수 있는 아이들을 충분히 방문하지 못하므로 $D_4 = D_5 = D_6 = -1$입니다.

시나리오 7에서 산타는 3개의 선물을 모두 나눠 주려면 첫 번째 집($X_{L_7} = 10$)까지 되돌아가야 하므로 $D_7 = 40$입니다.

시나리오 8에서는 되돌아갈 필요가 없어($X_{L_8} = X_8 = 40$) 3개의 선물을 모두 나눠 줄 수 있으므로 $D_8 = 35$입니다.