#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define for_(i, s, e) for (ll i = s; i < (ll)e; i++)
#define for__(i, s, e) for (ll i = s; i > (ll)e; i--)
#define mod(x) ((x) % MOD)
#define mid(x) midpoint(x)
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define bg begin()
#define ed end()
#define sz(a) int(a.size())
#define all(x) (x).bg, (x).ed
#define allr(x) x.rbegin(), x.rend()
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define nl "\n"
#define _ << ' ' <<
#define pb emplace_back
#define MP make_pair
#define UB upper_bound
#define LB lower_bound
#define ff first
#define ss second
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
const ll MOD = 1e9 + 7; // 998244353;
template <typename T1, typename T2>
inline istream &operator>>(istream &in, pair<T1, T2> &a)
{
in >> a.ff >> a.ss;
return in;
}
template <typename T1, typename T2>
inline ostream &operator<<(ostream &out, pair<T1, T2> a)
{
out << a.ff << " " << a.ss;
return out;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &v)
{
for_(i, 0, sz(v)) cin >> v[i];
return in;
}
template <typename T>
ostream &operator<<(ostream &out, vector<T> &v)
{
for_(i, 0, sz(v)) cout << v[i] << " ";
return out;
}
template <typename T1, typename T2>
pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return {l.ff + r.ff, l.ss + r.ss}; }
#define int long long
struct line
{
int m;
int c;
int num;
line(int _m, int _c, int _nm) : m(_m), c(_c), num(_nm) {}
friend double presek(const line l1, const line l2) { return (double)(l2.c - l1.c) / (double)(l1.m - l2.m); }
int operator()(int x) { return m*x + c; };
};
int32_t par[205][100005];
vector<int> dp1(100005);
vector<int> dp2(100005);
deque<line> dq;
void solve()
{
int n,k;cin>>n>>k;
vector<int>a(n+1,0);
for(int i=1;i<=n;i++) cin>>a[i];
vector<int>pref(n+1,0);
for(int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i];
for (int i = 1; i <= k+1; i++)
{
dq.clear();
for (int j = 1; j <= n; j++)
{
line tr(pref[j-1], dp1[j-1]-pref[n]*pref[j-1], j-1);
while (dq.size() >= 2 && presek(tr, dq[dq.size()-1]) <= presek(dq[dq.size()-2], tr))
dq.pop_back();
dq.push_back(tr);
while (dq.size() >= 2 && dq[0](pref[j]) <= dq[1](pref[j]))
dq.pop_front();
dp2[j] = dq[0](pref[j]) + pref[j]*pref[n]-pref[j]*pref[j];
par[i][j] = dq[0].num;
}
dp1 = dp2;
}
cout << dp1[n] << '\n';
int32_t tr = n;
for (int i = k+1; i > 1; i--)
{
tr = par[i][tr];
cout << tr << " ";
}
cout << "\n";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
cin >> tt;
while (tt--)
solve();
return 0;
}
