【题目描述】

小 $\zeta$ 来到了一个商店，商店里有 $n$ 个物品，每个物品的价值为一个 $[1,n]$ 中的整数，且所有物品的价值互不相同；每个物品的价格将为一个 $[1,10^9]$ 中的整数，保证对于所有 $1\leq x\leq n-1$，价值为 $x$ 的物品的价格一定不高于价值为 $x+1$ 的物品的价格。同时，商店里有 $n$ 柜台，柜台从 $1$ 到 $n$ 编号，每一个柜台可恰好存放一个物品。

小 $\zeta$ 将会按照编号从小到大的顺序依次遍历柜台，如果当前柜台上存放的物品的价值大于其当前购买的所有物品的价值的最大值，则他将会购买这个物品；反之，他将不会购买这个物品。商店获得的收益将为小 $\zeta$ 购买的物品的价格之和。

获取这个消息的商店老板小 $\gamma$ 于是想到一个主意，可以通过调整不同价值的物品在柜台里的摆放顺序来使得商店的利润最大化。同时，为了不让小 $\zeta$ 看出来商店里商品的拜访有蹊跷，对于其中一些柜台，小 $\gamma$ 规定了其必须摆放价值为定值的物品。

更具体的，小 $\gamma$ 的约束将通过一个值域在 $\{-1\}\cup [1,n]$ 中，且长度为 $n$ 的整数序列 $a$ 给出。对于所有 $1\leq i\leq n$，若 $1\leq a_i\leq n$，则表示要求第 $i$ 个柜台必须摆放价值为 $a_i$ 的物品；若 $a_i=-1$，则对第 $i$ 个柜台摆放的物品价值没有限制。小 $\gamma$ 保证对于所有 $1\leq x<y\leq n$，若 $a_x,a_y\not=-1$，则 $a_x\not=a_y$，因此不难证明总存在一个将 $n$ 个物品放入 $n$ 个柜台的方案，使得其满足其满足序列 $a$ 给出的约束。

由于小 $\zeta$ 其实很忙，所以他并不一定会逛完所有柜台。因此小 $\gamma$ 想要知道，对于所有 $1\leq i\leq n$，如果小 $\zeta$ 只按照编号从小到大的顺序遍历了编号在 $[1,i]$ 的柜台，那么在所有符合序列 $a$ 的约束条件的物品摆放方案中，商店能够获得的最大收益是多少，他希望你能够告诉他这个问题的答案。

【输入格式】

从文件 shop.in 中读入数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。特别的，样例的 $c$ 表示该样例与编号为 $c$ 的测试点的约束条件相同。

接下来依次输入每组测试数据，对于每组测试数据：

• 第一行包含一个正整数 $n$，表示物品数量；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示小 $\gamma$ 给出的约束序列 $a$；
• 第三行包含 $n$ 个正整数 $c_1,c_2,\ldots,c_n$，其中第 $i$ 个正整数 $c_i$ 表示价值为 $i$ 的物品的价格。

【输出格式】

输出到文件 shop.out 中。

对于每组测试数据，输出一行 $n$ 个非负整数，其中第 $i$ 个非负整数表示如果小 $\zeta$ 只按照编号从小到大的顺序遍历了编号在 $[1,i]$ 的柜台，在所有符合序列 $a$ 的约束条件的物品摆放方案中，商店能够获得的最大收益。

【样例输入1】

1 1
5
-1 -1 1 -1 -1
0 8 39 48 74

【样例输出1】

74 122 122 161 169

【样例解释1】

若小 $\zeta$ 仅遍历编号在 $[1,1]$ 的柜台，则小 $\gamma$ 的其中一种最优摆放方案满足柜台编号从小到大所摆放的物品价值分别为 $5\;4\;1\;2\;3$，此时取到最大收益 $74$。

若小 $\zeta$ 仅遍历编号在 $[1,2]$ 的柜台，则小 $\gamma$ 的其中一种最优摆放方案满足柜台编号从小到大所摆放的物品价值分别为 $4\;5\;1\;2\;3$，此时取到最大收益 $122$。

若小 $\zeta$ 仅遍历编号在 $[1,3]$ 的柜台，则小 $\gamma$ 的其中一种最优摆放方案满足柜台编号从小到大所摆放的物品价值分别为 $4\;5\;1\;2\;3$，此时取到最大收益 $122$。

若小 $\zeta$ 仅遍历编号在 $[1,4]$ 的柜台，则小 $\gamma$ 的其中一种最优摆放方案满足柜台编号从小到大所摆放的物品价值分别为 $3\;4\;1\;5\;2$，此时取到最大收益 $161$。

若小 $\zeta$ 仅遍历编号在 $[1,5]$ 的柜台，则小 $\gamma$ 的其中一种最优摆放方案满足柜台编号从小到大所摆放的物品价值分别为 $2\;3\;1\;4\;5$，此时取到最大收益 $169$。

【样例输入/输出2】

见选手目录下的 shop2.in/ans，该样例满足测试点 $1$ 的限制。

【样例输入/输出3】

见选手目录下的 shop3.in/ans，该样例满足测试点 $3$ 的限制。

【样例输入/输出4】

见选手目录下的 shop4.in/ans，该样例满足测试点 $5$ 的限制。

【样例输入/输出5】

见选手目录下的 shop5.in/ans，该样例满足测试点 $9$ 的限制。

【样例输入/输出6】

见选手目录下的 shop6.in/ans，该样例满足测试点 $12$ 的限制。

【样例输入/输出7】

见选手目录下的 shop7.in/ans，该样例满足测试点 $16$ 的限制。

【测试点约束】

对于所有测试数据，满足：

• $1\leq T\leq 10$；
• $1\leq n\leq 10^5$；
• 对于所有 $1\leq i\leq n$，满足 $1\leq a_i\leq n$ 或 $a_i=-1$；且对于所有 $1\leq x<y\leq n$，若 $a_x,a_y\not=-1$，则满足 $a_x\not=a_y$；
• 对于所有 $1\leq i\leq n$，满足 $1\leq c_i\leq 10^9$；且对于所有 $1\leq i\leq n-1$，满足 $c_i\leq c_{i+1}$。

每个测试点的具体限制如下表：

测试点编号	$n\le$	特殊性质
$1\sim 2$	$10$	无
$3\sim 4$	$100$
$5\sim 7$	$1000$
$8$	$10^5$	A
$9\sim 11$		B
$12\sim 15$		C
$16\sim 20$		无

特殊性质 A：对于所有 $1\leq i\leq n$，满足 $a_i=-1$。

特殊性质 B：对于所有 $1\leq i\leq n$，满足 $a_i\not=-1$ 的位置不超过 $100$ 个。

特殊性质 C：对于所有 $1\leq i\leq n$，满足 $c_i=1$。

samples