J. 划分区间
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定两个长度为 $$$n$$$ 的序列 $$$a_1,a_2,\cdots,a_n$$$ 和 $$$b_1,b_2,\cdots,b_n$$$。现在你可以将数组划分成若干段非空的不交区间，将这些区间按下标从小到大编号为 $$$1,2,\cdots,k$$$，其中第 $$$i$$$ 个区间 $$$[l, r]$$$ 的权值为 $$$\sum_{j=l}^r a_j\cdot b_i$$$。

现在，请求出对于序列 $$$a$$$ 恰好划分出 $$$k=1,2,\cdots,n$$$ 个区间的情况下，通过划分可能得到的最大权值之和是多少？

Input

第一行输入一个正整数 $$$T\ (1\le T\le 10^3)$$$，表示测试组数。

接下来 $$$T$$$ 组数据中，每组数据输入格式如下：

  • 第一行输入一个正整数 $$$n\ (1\le n\le 5000)$$$，表示序列长度。
  • 第二行输入 $$$n$$$ 个整数 $$$a_1,a_2,\dots,a_n\ (0\le |a_i|\le 10^6)$$$，表示 $$$a$$$ 序列。
  • 第三行输入 $$$n$$$ 个整数 $$$b_1,b_2,\dots,b_n\ (0\le |b_i|\le 10^6)$$$，表示 $$$b$$$ 序列。

此外，数据保证 $$$n^2$$$ 的总和不超过 $$$5000^2$$$。

Output

对于每组测试，每组测试输出一行 $$$n$$$ 个整数，第 $$$i$$$ 个整数表示恰好划分成 $$$i$$$ 个区间的最优划分能得到最大权值。

Example
Input
4
3
1 -5 2
1 -2 6
3
11 45 14
19 198 10
4
1 -2 -3 4
-1 2 3 -4
5
0 -1 2 0 30
100 2 3 1 1
Output
-2 7 23
1330 11891 9259
0 12 7 -30
3100 160 190 34 34