题目描述

众所周知，在平安夜，圣诞老人的工作是从精灵那里获取礼物，并将它们送给孩子们，为他们的内心带来欢乐与幸福。

城市中有 $N$ 座房子在笔直的道路上。房子编号从 $1\sim N$。

对于每座房子 $i$，已知：

• $X_i$：$X_i$ 表示第 $i$ 座房子沿道路的位置。
• $H_i\in \{0,1\}$；
• $V_i$。
  • 如果 $H_i = 0$，则第 $i$ 座房子中有一个精灵，持有一个价值为 $V_i$ 的礼物。
  • 如果 $H_i = 1$，则第 $i$ 座房子中有一个孩子，正在等待一个最小价值为 $V_i$ 的礼物。

共有 $N$ 个场景。在第 $i$ 个场景中，圣诞老人从坐标 $0$ 进入城市，携带一个空的礼物袋。他首先向右移动，直到到达第 $i$ 座房子（位于坐标 $X_i$），然后向左移动，直到到达某个其他位置 $X_{\text{left}_i} \leq X_i$。

• 当圣诞老人经过一个精灵的房子且之前未访问过时，他会拿走礼物并放入袋中。
• 当圣诞老人经过一个尚未收到礼物的孩子的房子时，他可以（但不必须）从袋中挑选一个当前存在的礼物交给孩子，并将该礼物从袋中移除。此操作仅在所选礼物的价值至少等于孩子指定的最小价值 $V$ 时才能完成。

在第 $i$ 个场景中，圣诞老人移动的总距离为 $D_i = 2X_i - X_{\text{left}_i}$。你的任务是：针对每个场景，找到圣诞老人分发所有精灵礼物所需的最小距离 $D_i$。

• 注意：允许某些孩子未收到礼物，但必须满足所有礼物已被分发，且每个孩子至多收到一个礼物。
• 如果无法满足条件，则设 $D_i = -1$。特别地，若圣诞老人无法到达所有精灵的房子，则必然无法满足条件。

输入格式

本题单个测试点内有多组测试数据。

第一行输入包含一个整数 $T$（$1 \leq T \leq 10$），表示测试数据组数。

随后描述 $T$ 组数据。每组数据包含四行：

• 第一行，一个整数 $N$，城市中的房子数量。
• 第二行， $N$ 个整数 $X_1, X_2, \dots, X_N$。
• 第三行， $N$ 个整数 $H_1, H_2, \dots, H_N$。
• 第四行， $N$ 个整数 $V_1, V_2, \dots, V_N$。

输出格式

每组数据，输出一行 $N$ 个整数：$D_1, D_2, \dots, D_N$。

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

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

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

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

提示

样例解释

样例 $1$ 解释

样例 $1$ 第一组数据中，共有 $8$ 座房子。第 $2$、$3$ 和 $4$ 座房子中有 $3$ 个精灵，分别持有价值为 $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$ 中，圣诞老人需要返回到第 $1$ 座房子（$X_{\text{Left}_7} = 10$）以分发全部 $3$ 份礼物，因此 $D_7 = 40$。
• 在场景 $8$ 中，圣诞老人完全无需折返（$X_{\text{Left}_8} = X_8 = 40$）即可分发所有 $3$ 份礼物，因此 $D_8 = 35$。

数据范围

对于 $100\%$ 的数据，保证：

• $1\le T\le 10$；
• $1\le N\le 96\, 068$；
• $1\le \sum N\le 5\times 10^5$；
• $0\le X_1\le X_2\le \ldots\le X_N\le 10^9$；
• $H_i\in \{0,1\}$；
• $0\le V_i\le N$；

子任务

编号	$N\le$	分值
$1$	$84$	$10$
$2$	$169$
$3$	$1\, 379$
$4$	$2\, 709$
$5$	$5\, 562$
$6$	$13\, 123$
$7$	$27\, 599$
$8$	$41\, 646$
$9$	$95\, 045$
$10$	$96\, 068$