题目描述

题目译自 Romanian Master of Informatics 2019 Day2 T3 「Santa Claus」

众所周知，每逢平安夜，圣诞老人的任务就是从精灵那里拿到礼物，分发给孩子们，为他们带来欢乐与幸福。

在一个城市里，有一条路上分布着 $N$ 座房子，编号从 $1$ 到 $N$。对于每座房子 $i$，我们给出三个整数 $X_i, H_i, V_i$，其中 $X_i$ 是第 $i$ 座房屋在路上的位置。如果 $H_i=0$，则第 $i$ 座房屋中有一个精灵，带着一份价值为 $V_i$ 的礼物。如果 $H_i=1$，则第 $i$ 座房屋中有一个孩子，期待收到一份价值至少为 $V_i$ 的礼物。

任务包含 $N$ 个场景。在第 $i$ 个场景中，圣诞老人从坐标 $0$ 进入城市，背着一个空礼袋。他先向右走，直到到达第 $i$ 座房子（坐标为 $X_i$），然后向左走，直到某个位置 $xLeft_i\leq X_i$。沿途：

• 经过未拜访过的精灵房子时，他会拿起礼物放进礼袋；
• 经过未收到礼物的孩子房子时，他可以（但不必须）从礼袋中选一份礼物送给孩子，并将其从袋中移除，前提是礼物的价值不低于孩子要求的 $V_i$。

在第 $i$ 个场景中，圣诞老人行走的总距离为 $D_i = 2X_i- xLeft_i$。你的任务是找出每个场景中，圣诞老人分发所有精灵礼物所需的最短距离 $D_i$。注意，有些孩子可能收不到礼物，这没关系，只要所有礼物都分发出去，且每个孩子最多收到一份礼物。如果不存在这样的 $D_{i}$，则令 $D_{i}=-1$。特别地，对于圣诞老人无法到达所有精灵房屋的情况，则 $D_i=-1$。

输入格式

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

每组输入数据第一行包含一个整数 $N$ $(1 \leq N \leq 96068)$，表示城市中的房屋数量。

第二行包含 $N$ 个整数 $X_1, X_2, \ldots, X_N$ $(0 \leq X_{1} \leq X_{2} \leq \ldots \leq X_N \leq 10^9)$。

第三行包含 $N$ 个整数 $H_1,H_2,\ldots H_N$ $(0 \leq H_i \leq 1)$。

第四行包含 $N$ 个整数 $V_1,V_2,\ldots V_N$ $(0 \leq V_i \leq N)$。

所有输入数据组的 $N$ 值的总和不超过 $5\cdot 10^5$。

输出格式

对于每组输入数据，输出一行 $N$ 个整数 $D_{1}, D_{2}, \ldots, 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

在样例 1 中，有 $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$：圣诞老人需返回到第一座房子（$xLeft_7 = 10$）以分发所有 3 份礼物，$D_7 = 40$；
• 场景 $8$：圣诞老人无需返回（$xLeft_8 = X_8 = 40$），即可分发所有礼物，$D_8 = 35$。

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$	$10$	$1 \leq N \leq 84$
$2$	$10$	$1 \leq N \leq 169$
$3$	$10$	$1 \leq N \leq 1379$
$4$	$10$	$1 \leq N \leq 2709$
$5$	$10$	$1 \leq N \leq 5562$
$6$	$10$	$1 \leq N \leq 13123$
$7$	$10$	$1 \leq N \leq 27599$
$8$	$10$	$1 \leq N \leq 41646$
$9$	$10$	$1 \leq N \leq 95045$
$10$	$10$	$1 \leq N \leq 96068$