/*
Given K sorted arrays, possibly of different sizes, merge them and print the sorted output.

Input format
First line contains an integer K - Number of arrays.

For each array there is two lines of input:

First line contains an integer n - Size of array.

Second line contains n integers - The array.

Output format
Print in single line, the elements in sorted order.

Sample Input 1
3

3

2 4 7

1

8

4

2 5 5 9

Sample Output 1
2 2 4 5 5 7 8 9

Explanation
Elements of 1st array - 2, 4, 7.

Elements of 2nd array - 8.

Elements of 3rd array - 2, 5, 5, 9.

Merging the elements and printing them in sorted order will give - 2, 2, 4, 5, 5, 7, 8, 9.

Constraints
1 <= K <= 10^5

1 <= n <= 10^5

-10^6<= Array elements <= 10^6

Note: Total number of elements will be less than 10^6.
*/

struct comparator{
    bool operator()(pair<int, pair<int,int>>&p1,pair<int, pair<int,int>>&p2){
        return p1.first>p2.first;
    }
};

vector<int> mergeKSortedArrays(vector<vector<int>> arrays){
    vector<int>ans;
    int k=arrays.size();
    int i,j;
    priority_queue< pair<int, pair<int,int>>,
    vector< pair<int, pair<int,int>> >,
    comparator
    > pq;
    // pair< arr[i][j],pair<i,j>>
    // arr[i][j] : jth value in i-th array
    // i: i-th array (arrayIndex)
    // j: IndexInArray
    for(i=0;i<k;i++){
        // if(arrays[i].size()>0)
         pq.push({arrays[i][0],{i,0}});
    }

    while(!pq.empty()){
        auto top=pq.top();
        pq.pop();
        int value=top.first;
        int arrayIndex=top.second.first;
        int IndexInArray=top.second.second;
        int currentArraySize=arrays[arrayIndex].size();


        ans.push_back(value);

        if(IndexInArray+1<currentArraySize){
            int newValue=arrays[arrayIndex][IndexInArray+1];
            pq.push({newValue,{arrayIndex,IndexInArray+1}});
        }
    }

        return ans;

}