#include<iostream>
#include<queue>
#include<vector>
using namespace std;

typedef pair<int, pair<int,int> > node;
vector<int> mergeKSortedArray(vector<vector<int> > arr){
    vector<int>result;
    priority_queue<node, vector<node>, greater<node> > pq;//min priority queue
    //insert 0th element of each arr to pq
    for(int i=0;i<arr.size();i++){
        pq.push({arr[i][0],{i,0}});//we need to store 3 things - val of ele, index of arr, index of ele
    }
    //remove the ele one by one from min heap and add it to the result vector
    while(!pq.empty()){
        node current = pq.top();
        pq.pop();
        int element = current.first;
        int x = current.second.first;//row in which element is present
        int y = current.second.second;//col in which element is present

        result.push_back(element);
        //you need to push in pq the next element of current x,y+1
        if(y+1<arr.size()){
            pq.push({arr[x][y+1],{x,y+1}});
        }
    }
    return result;
}
int main(){
    vector<vector<int> >arr{{2,6,12,15},
                            {1,3,14,20},
                            {3,5,8,10}};

    vector<int>output = mergeKSortedArray(arr);
    for(auto x:output){
        cout<<x<<" ";
    }



return 0;}