9653 - LIS

给定序列 A,序列中的每一项 A_i 有删除代价 B_i 和附加属性 C_i。请删除若干项,使得 A 的最长上升子序列长度减少至少 1,且付出的代价之和最小,并输出方案。

如果有多种方案,请输出将删去项的附加属性排序之后,字典序最小的一种。

输入

输入包含多组数据。

输入的第一行包含整数 T,表示数据组数。接下来 4T 行描述每组数据。

每组数据的第一行包含一个整数 N,表示 A 的项数。

接下来三行,每行 N 个整数 A_1\sim A_nB_1\sim B_nC_1\sim C_n,满足 1\le A_i,B_i,C_i \le 10^9,且 C_i 两两不同。

输出

对每组数据,输出两行。第一行包含两个整数 S,M,依次表示删去项的代价和与数量;接下来一行 M 个整数,表示删去项在 A 中的的位置,按升序输出。

样例

输入

1
6
3 4 4 2 2 3
2 1 1 1 1 2
6 5 4 3 2 1

输出

4 3
2 3 6

提示

删去 (A_2,A_3,A_6),(A_1,A_6),(A_2,A_3,A_4,A_5) 等都是合法的方案,但(A_2,A_3,A_6) 对应的 C 值的字典序最小。

对于 100\% 的数据,1\le N\le 7001\le T\le 5

来源

山东省选

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题