题目描述

给出一个长度为 $n$ 的序列 $a$。定义其前缀和数组 $b_i=\sum_{j=1}^ia_j$。定义其权值 $S=\sum_{i=1}^n(b_i\bmod 2)$。

你可以对序列 $a$ 进行若干次如下操作：

• 交换 $a_i,a_j$，花费 $c_i+c_j$ 元，其中 $c$ 为给定序列；

对于 $i=0\sim n$，求使得 $S=i$ 的最少钱数。如果不可能，输出 $-1$。

输入格式

本题包含多组测试数据。

第一行一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行一个正整数 $n$，表示序列长度。

第二行 $n$ 个正整数，表示序列 $a$。

第三行 $n$ 个正整数，表示序列 $c$。

输出格式

对于每组测试数据：

一行，$n+1$ 个整数，第 $i$ 个表示 $S=i-1$ 的最少钱数。如果不可能，输出 $-1$。

3
3
1 2 3
1 1 1
5
1 2 3 4 5
2 5 3 6 4
10
1 8 3 5 2 6 3 4 6 2
3 2 7 1 8 2 5 8 3 1

-1 2 0 -1
-1 -1 7 0 9 -1
-1 -1 5 3 4 0 7 8 6 -1 -1

提示

【样例解释】

对于第一组数据，初始 $\sum_{i=1}^n(b_i\bmod 2)=2$，故使 $S=2$ 最少要花 $0$ 元。

交换 $a_1,a_2$ 即可使 $\sum_{i=1}^n(b_i\bmod 2)=1$，故使 $S=1$ 可以花费 $2$ 元。可以证明这是最优解。

可以证明不存在交换方案使得 $S=0$ 或 $S=3$。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\leq n,\sum n\leq500$，$1\leq a_i\leq10^9$，$1\leq c_i\leq10^6$，$1\leq T\leq500$。