Divide to k heaps in O(2^n * n)

//#pragma optimization_level 3
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <fstream>
#include <cmath>
#include <string>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string.h>
#include <stack>
#include <assert.h>
#include <list>
#include <time.h>
#include <memory>
#include <chrono>
using namespace std;
//
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
//#define cin in
//#define cout out
#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define ms multiset
#define pb push_back
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define PI acos(-1.0)
//#define sort(a, b) sort(a.begin(), a.end(), b())
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("input.txt");
ofstream out("output.txt");

// divides balls to 'k' heaps in O(2^n * n)

vector<int> sum;
vector<int> sm;
vector<int> weight;
int n, m_cnt, full_mask;
int k;

bool is_bit(int a, int p) {
    return (a >> p) % 2;
}

void precalc_sums() {
    for (int mask = 0; mask < m_cnt; ++mask) {
        for (int bit = 0; bit < n; ++bit) {
            if (is_bit(mask, bit))
                sum[mask] += weight[bit];
        }
    }
}

void bfs() {
    queue<int> q;
    stack<int> nxt;

    int w = sum[full_mask] / k;

    for (int mask = 0; mask < m_cnt; ++mask) {
        if (sum[mask] == w)
            q.push(mask);
    }

    for (int cur_w = w; cur_w <= sum[full_mask]; cur_w += w) {

        while (!q.empty() && sum[q.front()] < cur_w + w) {
            int mask = q.front();
            q.pop();

            for (int bit = 0; bit < n; ++bit) {
                if (is_bit(mask, bit)) continue;
                int n_mask = mask | (1 << bit);

                if (sm[n_mask] || sum[n_mask] > cur_w + w) continue;

                if (sum[mask] == cur_w)
                    sm[n_mask] = mask;
                else if (sm[mask])
                    sm[n_mask] = sm[mask];

                if (sum[n_mask] == cur_w + w)
                    nxt.push(n_mask);
                else
                    q.push(n_mask);
            }
        }

        if (nxt.empty()) break;
        while (!nxt.empty()) {
            q.push(nxt.top());
            nxt.pop();
        }
    }
}

int main() {
    cin >> n >> k;
    weight.resize(n);
    for (int& w : weight) cin >> w;
    m_cnt = (1 << n);
    sum.resize(m_cnt, 0);
    sm.resize(m_cnt, 0);

    precalc_sums();
    full_mask = (1 << n) - 1;

    if (sum[full_mask] % k) {
        cout << "Impossible";
    } else {
        bfs();

        if (!sm[full_mask]) {
            cout << "Impossible";
            return 0;
        }

        int w = sum[full_mask] / k;

        int mask = full_mask;
        while (sum[mask] != 0) {
            int cur = mask ^ sm[mask];
            for (int bit = 0; bit < n; ++bit) {
                if (is_bit(cur, bit))
                    cout << weight[bit] << ' ';
            }
            cout << '\n';

            mask = sm[mask];
        }
    }
}