Description

寫一個程序來模擬操作系統的進程調度。假設該系統只有一個CPU，每一個進程的到達時間，執行時間和運行優先級都是已知的。其中運行優先級用自然數表示，數字越大，則優先級越高。如果一個進程到達的時候CPU是空閑的，則它會一直占用CPU直到該進程結束。除非在這個過程中，有一個比它優先級高的進程要運行。在這種情況下，這個新的（優先級更高的）進程會占用CPU，而老的只有等待。如果一個進程到達時，CPU正在處理一個比它優先級高或優先級相同的進程，則這個（新到達的）進程必須等待。一旦CPU空閑，如果此時有進程在等待，則選擇優先級最高的先運行。如果有多個優先級最高的進程，則選擇到達時間最早的。

Input

輸入文件包含若干行，每一行有四個自然數（均不超過108），分別是進程號，到達時間，執行時間和優先級。不同進程有不同的編號，不會有兩個相同優先級的進程同時到達。輸入數據已經按到達時間從小到大排序。輸入數據保證在任何時候，等待隊列中的進程不超過15000個。

Output

按照進程結束的時間輸出每個進程的進程號和結束時間

Sample Input

Sample Output

#include<cstdio>#include<queue>#define min(a,b) ((a)<(b)? (a):(b))using namespace std;const int maxx = 15000 + 10;struct PRogram{    int id,come,time,imp;    program(int id=0,int come=0,int time=0,int imp=0):    id(id),come(come),time(time),imp(imp){}; };bool Operator < (program a,program b){    if(a.imp!=b.imp) return a.imp<b.imp;    return a.come>b.come;}priority_queue<program> que;int final;int main(){    //freopen("system.in","r",stdin);    //freopen("system.out","w",stdout);        int id,come,time,imp;        while(~scanf("%d%d%d%d",&id,&come,&time,&imp))    {        while(!que.empty()&&final<come)        {            program now=que.top();            que.pop();                    if(final<now.come)             final=now.come;                    int dis=min(now.time,come-final);            now.time-=dis; final+=dis;                    if(now.time) que.push(now);            else printf("%d %d/n",now.id,final);        }        que.push(program(id,come,time,imp));    }        while(!que.empty())    {        program now = que.top();        que.pop();        final+=now.time;        printf("%d %d/n",now.id,final);    }         return 0;}