P12091 [RMI 2019] 圣诞老人 / Santa Claus

众所周知，在平安夜，圣诞老人的工作是从精灵那里获取礼物，并将它们送给孩子们，为他们的内心带来欢乐与幸福。 城市中有 $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$。

### 样例解释 #### 样例 $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$ | $10$ | | $3$ | $1\, 379$ | $10$ | | $4$ | $2\, 709$ | $10$ | | $5$ | $5\, 562$ | $10$ | | $6$ | $13\, 123$ | $10$ | | $7$ | $27\, 599$ | $10$ | | $8$ | $41\, 646$ | $10$ | | $9$ | $95\, 045$ | $10$ | | $10$ | $96\, 068$ | $10$ |