FRiiCJ - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define yes cout << "YES\n";
#define no cout << "NO\n";


void FastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void solve(){
    int n; cin >> n;
    vector<vector<int>> a(n);
    int maxlen = 0;
    for (int i = 0; i < n; ++i){
        int k; cin >> k;
        a[i].resize(k);
        for (int j = 0; j < k; ++j){
            cin >> a[i][j];
        }
        maxlen = max(maxlen, k);
    }

    vector<char> used(n, 0);
    vector<int> order;
    int covered = 0;

    auto suffix_less = [&](int i, int j, int c)->bool{
        int li = (int)a[i].size();
        int lj = (int)a[j].size();
        int upto = min(li, lj);
        for (int p = c; p < upto; ++p){
            if (a[i][p] < a[j][p]) return true;
            if (a[i][p] > a[j][p]) return false;
        }
        if (li != lj) return li < lj;
        return i < j;
    };

    while (covered < maxlen){
        int best = -1;
        for (int i = 0; i < n; ++i){
            if (used[i]) continue;
            if ((int)a[i].size() <= covered) continue;
            if (best == -1) best = i;
            else if (suffix_less(i, best, covered)) best = i;
        }
        if (best == -1) break;
        used[best] = 1;
        order.push_back(best);
        covered = max(covered, (int)a[best].size());
    }
    for (int i = 0; i < n; ++i) if (!used[i]) order.push_back(i);

    vector<int> bottom;
    bottom.reserve(maxlen);
    for (int j = 0; j < maxlen; ++j){
        int val = 0;
        bool found = false;
        for (int idx : order){
            if ((int)a[idx].size() > j){
                val = a[idx][j];
                found = true;
                break;
            }
        }
        if (found) bottom.push_back(val);
        else bottom.push_back(0);
    }

    for (int i = 0; i < (int)bottom.size(); ++i){
        if (i) cout << ' ';
        cout << bottom[i];
    }
    cout << '\n';
}

signed main(){
    FastIO();

    int t;
    cin >> t;

    while (t--){
        solve();
    }
    return 0;
}