#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <vector>
#include <iostream>

using namespace std;
typedef unsigned int uint;

struct payload
{
	uint number;
	uint i;
	uint j;
};

struct heap
{
	struct payload *data;
	uint size;
	uint idx;
};

struct heap init(uint n);
void destroy(struct heap h);
void sift(struct heap *h, uint idx);
void percolate(struct heap *h, uint idx);
void add(struct heap *h, struct payload p);
void cut(struct heap *h, uint idx);
void heapify(struct heap *h);

#define INF 112131231313

/*
k-way merge
Ce este: Acest algoritm va interclasa n siruri sortate intr-un singur sir sortat.
Complexitate: O(n*k*log(k)), unde k = nr de siruri si n = lungimea fiecarui sir. Aceasta compelxitate
              este valabila doar daca folosim un min-heap care ne lasa sa determinam minimul in O(1)
Algoritm:
	Pentru a implementa aceast algoritm vom folosi un min-heap.
*/

void kwaymerge(vector<vector<int> > v, int total, FILE *out);

int main(void)
{
	FILE *in = fopen("interclasari.in", "r");
	FILE *out = fopen("interclasari.out", "w");
	if(in != NULL && out != NULL)
	{
        int k;
        fscanf(in, "%d%*c", &k);
        vector<vector<int> > v;
        int sum = 0;
        for(int i = 0; i < k; i++)
        {
            int n;
            fscanf(in, "%d%*c", &n);
            sum += n;
            vector<int> kp;
            for(int j = 0; j < n; j++)
            {
                int t;
                fscanf(in, "%d%*c", &t);
                kp.push_back(t);
            }
            v.push_back(kp);
        }

        kwaymerge(v, sum, out);

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("Error\n");
	}

	return 0;
}

void kwaymerge(vector<vector<int> > v, int total, FILE *out)
{
    // Cream heap-ul
    struct heap h = init(v.size());

    for(int i = 0; i < v.size(); i++)
    {
        struct payload p;
        if(v[i].size())
        {
            p.number = v[i][0];
            p.i = i;
            p.j = 0;
            add(&h, p);
        }
    }
    fprintf(out, "%d\n", total);

    for(int i = 0; i < total; i++)
    {
        struct payload root = h.data[0];
        cut(&h, 0);

        fprintf(out, "%d ", root.number);

        if(root.j < v[root.i].size())
        {
            root.j++;
            root.number = v[root.i][root.j];
        }
        else
        {
            root.number = INF;
        }

        add(&h, root);
    }

    destroy(h);
}

// Organizeaza nodurile heap-ului pe nivele
void heapify(struct heap *h)
{
	int i = h->size / 2;
	for(; i > 0; i--)
	{
		sift(h, i);
	}
}

void cut(struct heap *h, uint k)
{
	h->data[k] = h->data[h->idx - 1];
	h->size--;
	h->idx--;

	// Acum testam ce trebuie sa facem cu frunza pe care am folosite, anume:
	//  a) s-o urcam: percolate
	//  b) s-o cernem: sift
	if(k > 1 && (h->data[k].number > h->data[k / 2].number))
	{
		percolate(h, k);
	}
	else
	{
		sift(h, k);
	}
}

void add(struct heap *h, struct payload p)
{
	if((h->idx + 1) >= h->size)
	{
		h->size += 12;
		h->data = (struct payload *)realloc(h->data, sizeof(struct payload) * h->size);
		if(h->data == NULL)
		{
			printf("Failed to realloc\n");
		}
	}
	h->data[h->idx++] = p;
	percolate(h, h->idx - 1);
}

void percolate(struct heap *h, uint k)
{
	struct payload key = h->data[k];
	while(k >= 1 && key.number < h->data[k / 2].number)
	{
		h->data[k] = h->data[k / 2];
		k = k / 2;
	}
	h->data[k] = key;
}

void sift(struct heap *h, uint idx)
{
	int son = 0;
	do
	{
		son = 0;
		if((idx * 2) < h->idx)
		{
			son = idx * 2;

			if((2 * idx + 1) < h->idx)
			{
				uint right_child = 2 * idx + 1;
				if(h->data[right_child].number < h->data[son].number)
				{
					son = right_child;
				}
			}

			if(h->data[son].number >= h->data[idx].number)
			{
				son = 0;
			}
		}

		if(son)
		{
			struct payload temp = h->data[son];
			h->data[son] = h->data[idx];
			h->data[idx] = temp;
			idx = son;
		}
	}while(son);
}

void destroy(struct heap h)
{
	free(h.data);
}

struct heap init(uint n)
{
	struct heap h;
	h.size = n;
	h.idx = 0;
	h.data = (struct payload *)malloc(sizeof(struct payload) * n);
	if(h.data != NULL)
	{
		return h;
	}
	else
	{
		printf("Failed to init the heap\n");
	}
	return h;
}