class HeapNode {
    public int value;
    public int arrNum;
    public int index;

    public HeapNode(int value, int arrNum, int index) {
        this.value = value;
        this.arrNum = arrNum;
        this.index = index;
    }
}
public static void printTopK(int[][] matrix,int topK) {
        int heapSize = matrix.length;
        HeapNode[] heapNodes = new HeapNode[heapSize];
        for (int i = 0; i < heapSize; i++) {
            heapNodes[i] = new HeapNode(matrix[i][matrix[i].length-1], i, matrix[i].length-1);
            insertHeap(heapNodes, i);
        }
        for (int i = 0; i < topK; i++) {
            if (heapSize==0) {
                break;
            }
            System.out.println(heapNodes[0].value);
            if (heapNodes[0].index!=0) {
                heapNodes[0] = new HeapNode(matrix[heapNodes[0].arrNum][heapNodes[0].index-1], heapNodes[0].arrNum, heapNodes[0].index-1);
            } else {
                swap(heapNodes, 0, --heapSize);
            }
            heapify(heapNodes, 0, heapSize);
        }
    }
    public static void swap(HeapNode[] heap,int index1,int index2) {
        HeapNode tempHeapNode = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = tempHeapNode;
    }
    public static void insertHeap(HeapNode[] heap,int index) {
        while (index != 0) {
            if (heap[(index-1)/2].value<heap[index].value) {
                swap(heap, (index-1)/2, index);
            } else {
                break;
            }
        }
    }
    public static void heapify(HeapNode[] heapNodes,int index,int heapSize) {
        int largest = index;
        int left =  index*2+1;
        int right = index*2+2;
        while (left<heapSize) {
            if (heapNodes[index].value<heapNodes[left].value) {
                largest = left;
            }
            if (right<heapSize&& heapNodes[index].value<heapNodes[right].value) {
                largest = right;
            }
            if (largest!=index) {
                swap(heapNodes, largest, index);
            } else {
                break;
            }
            index = largest;
            left = index*2+1;
            right = index*2+2;
        }
    }