给定 $n$ 个非负整数三元组 $a_i, b_i, c_i$ ($1 \le i \le n$) 和一个正整数 $k \le n$。你的任务是找到一组下标 $1 \le i_1 < i_2 < \dots < i_k \le n$，使得下式的值最大： $$\left(\sum_{j=1}^k a_{i_j}\right)^2 + \left(\sum_{j=1}^k b_{i_j}\right)^2 + \left(\sum_{j=1}^k c_{i_j}\right)^2$$ 输出该和的最大可能值。

输入格式

输入的第一行包含一个正整数 $T$，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 40$)。接下来的 $n$ 行，每行包含三个非负整数 $a_i, b_i$ 和 $c_i$ ($0 \le a_i, b_i, c_i \le 10^6$)。 保证输入中所有 $n$ 的总和不超过 $200$。

输出格式

对于每个测试用例，第一行输出一个整数：问题的答案。下一行输出 $k$ 个整数 $1 \le i_1 < i_2 < \dots < i_k \le n$，表示取得该答案的下标集合。

样例

输入 1

2
3 1
4 2 6
4 9 7
6 4 2
3 2
7 3 2
8 2 4
4 7 9

输出 1

146
2
394
2 3