import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * author：左程云
 */
public class SDEandPM {

    public static class Program {
        public int index;
        public int pm;
        public int start;
        public int rank;
        public int cost;

        public Program(int index, int pmNum, int begin, int rank, int cost) {
            this.index = index;
            this.pm = pmNum;
            this.start = begin;
            this.rank = rank;
            this.cost = cost;
        }
    }

    public static class PmLoveRule implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            if (o1.rank != o2.rank) {
                return o1.rank - o2.rank;
            } else if (o1.cost != o2.cost) {
                return o1.cost - o2.cost;
            } else {
                return o1.start - o2.start;
            }
        }

    }

    // 大黑盒
    // 每一个pm，有自己的堆(PmLoveRule)
    // 每一个pm的堆里有堆顶，所有的堆顶会再组成一个，程序员堆(程序员喜好)
    // void add(...)  项目  pop()
    public static class BigQueues {
        //  PriorityQueue<Program> pmQ = pmQueues.get(i);
        private List<PriorityQueue<Program>> pmQueues;
        // 程序员堆（一个，程序员共享池）
        private Program[] sdeHeap;
        // indexes[i] -> i号pm的堆顶项目，在sde堆中处在啥位置
        private int[] indexes;
        private int heapsize; // 程序员堆的大小

        public BigQueues(int pmNum) {
            heapsize = 0;
            sdeHeap = new Program[pmNum];
            indexes = new int[pmNum + 1];
            for (int i = 0; i <= pmNum; i++) {
                indexes[i] = -1;
            }
            pmQueues = new ArrayList<>();
            // i  pmQueues.get(i)
            for (int i = 0; i <= pmNum; i++) {
                pmQueues.add(new PriorityQueue<Program>(new PmLoveRule()));
            }
        }

        // 当前是否有项目可以弹出被程序员做
        public boolean isEmpty() {
            return heapsize == 0;
        }

        /**
         * 加入对应项目经理的项目池，同时更新程序员池子
         *
         * @param program
         */
        public void add(Program program) {
            PriorityQueue<Program> pmHeap = pmQueues.get(program.pm);
            pmHeap.add(program);
            // 有可能当前的项目，成了此时pm最喜欢的项目，换堆顶，调整sde堆中的项目
            Program head = pmHeap.peek(); // 现在的堆顶
            // 之前pm在sde堆中的自己的堆顶，sde？
            int heapindex = indexes[head.pm];
            if (heapindex == -1) { // 之前没堆顶,
                sdeHeap[heapsize] = head;
                indexes[head.pm] = heapsize;
                heapInsert(heapsize++);
            } else { // 加此时的program之前，我有老堆顶
                sdeHeap[heapindex] = head;
                heapInsert(heapindex);
                heapify(heapindex);
            }
        }

        // 程序员挑项目，返回挑选的项目
        public Program pop() {
            Program head = sdeHeap[0];
            PriorityQueue<Program> queue = pmQueues.get(head.pm);
            queue.poll();
            if (queue.isEmpty()) { // 此时的pm手上没有项目了
                swap(0, heapsize - 1);
                sdeHeap[--heapsize] = null;
                indexes[head.pm] = -1;
            } else {
                sdeHeap[0] = queue.peek();
            }
            heapify(0);
            return head;
        }

        private void heapInsert(int index) {
            while (index != 0) {
                int parent = (index - 1) / 2;
                if (sdeLoveRule(sdeHeap[parent], sdeHeap[index]) > 0) {
                    swap(parent, index);
                    index = parent;
                } else {
                    break;
                }
            }
        }

        private void heapify(int index) {
            int left = index * 2 + 1;
            int right = index * 2 + 2;
            int best = index;
            while (left < heapsize) {
                if (sdeLoveRule(sdeHeap[left], sdeHeap[index]) < 0) {
                    best = left;
                }
                if (right < heapsize && sdeLoveRule(sdeHeap[right], sdeHeap[best]) < 0) {
                    best = right;
                }
                if (best == index) {
                    break;
                }
                swap(best, index);
                index = best;
                left = index * 2 + 1;
                right = index * 2 + 2;
            }
        }

        private void swap(int index1, int index2) {
            Program p1 = sdeHeap[index1];
            Program p2 = sdeHeap[index2];
            sdeHeap[index1] = p2;
            sdeHeap[index2] = p1;
            indexes[p1.pm] = index2;
            indexes[p2.pm] = index1;
        }

        private int sdeLoveRule(Program p1, Program p2) {
            if (p1.cost != p2.cost) {
                return p1.cost - p2.cost;
            } else {
                return p1.pm - p2.pm;
            }
        }

    }

    public static class StartRule implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.start - o2.start;
        }

    }

    public static int[] workFinish(int pms, int sdes, int[][] programs) {
        /**
         * 将所有项目放入队列
         */
        PriorityQueue<Program> startQueue = new PriorityQueue<Program>(new StartRule());
        for (int i = 0; i < programs.length; i++) {
            Program program = new Program(
                    i, programs[i][0], programs[i][1], programs[i][2], programs[i][3]);
            startQueue.add(program);
        }

        /**
         * 程序员在1的时间点都可以工作
         */
        PriorityQueue<Integer> wakeQueue = new PriorityQueue<Integer>();
        for (int i = 0; i < sdes; i++) {
            wakeQueue.add(1);
        }

        BigQueues bigQueues = new BigQueues(pms);
        int finish = 0; /
        int[] ans = new int[programs.length];
        while (finish != ans.length) {
            /**
             * 最早可以工作的程序员的时间点，推动时间线
             */
            int sdeWakeTime = wakeQueue.poll();

            /**
             * 如果项目池里有项目可以启动，则添加到大队列
             */
            while (!startQueue.isEmpty()) {
                if (startQueue.peek().start > sdeWakeTime) {
                    break;
                }
                bigQueues.add(startQueue.poll());
            }
            //
            if (bigQueues.isEmpty()) { // 当前时间点并无项目可做
                wakeQueue.add(startQueue.peek().start);
            } else { // 当前时间点有项目可做
                Program program = bigQueues.pop();
                ans[program.index] = sdeWakeTime + program.cost;
                wakeQueue.add(ans[program.index]);
                finish++;
            }
        }
        return ans;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void main(String[] args) {
        int pms = 2;
        int sde = 2;
        int[][] programs = {{1, 1, 1, 2}, {1, 2, 1, 1}, {1, 3, 2, 2}, {2, 1, 1, 2}, {2, 3, 5, 5}};
        int[] ans = workFinish(pms, sde, programs);
        printArray(ans);
    }

}