Priest John's Busiest DayTime Limit: 2000MSMemory Limit: 65536KTotal Submissions: 5263Accepted: 1828Special Judge

Description

John is the only priest in his town. September 1st is the John's busiest day in a year because there is an old legend in the town that the couple who get married on that day will be forever blessed by the God of Love. This year N couples plan to get married on the blessed day. The i-th couple plan to hold their wedding from time S_i to time T_i. According to the traditions in the town, there must be a special ceremony on which the couple stand before the priest and accept blessings. The i-th couple need D_i minutes to finish this ceremony. Moreover, this ceremony must be either at the beginning or the ending of the wedding (i.e. it must be either from S_i to S_i + D_i, or from T_i - D_i to T_i). Could you tell John how to arrange his schedule so that he can present at every special ceremonies of the weddings.

Note that John can not be present at two weddings simultaneously.

Input

The first line contains a integer N ( 1 ≤ N ≤ 1000).

The next N lines contain the S_i, T_i and D_i. S_i and T_i are in the format of hh:mm.

Output

The first line of output contains "YES" or "NO" indicating whether John can be present at every special ceremony. If it is "YES", output another N lines describing the staring time and finishing time of all the ceremonies.

Sample Input

208:00 09:00 3008:15 09:00 20

Sample Output

YES08:00 08:3008:40 09:00

Source

, Dagger and Facer __________________________________________

1 Program Stone;  2 var n,le,deep,lt,i,j:longint;  3     si,ti:array[1..1000]of longint;  4     d:array[1..1000]of longint;  5     map:array[1..2000,1..2000]of boolean;  6     fs,fv:array[1..2000]of boolean;  7     head,dfn,low,tr,rd,stack:array[1..2000]of longint;  8     next,date:array[1..4000000]of longint;  9  function judge(asi,ati,bsi,bti:longint):boolean;        //判断两个时间段是否冲突 10   begin 11     if ((asi
     
      
       
        
         n then i:=stack[le]-n else i:=stack[le]+n; 68       if tr[i]=lt then begin 69                          writeln('NO'); 70                          halt; 71                        end; 72       fs[stack[le]]:=false; 73       dec(le); 74     until stack[le+1]=x; 75   end; 76  77  function min(a,b:longint):longint; 78   begin 79     if a
         0 do 94      begin 95       if fv[date[i]] then begin 96                            tarjan(date[i]); 97                            low[x]:=min(low[x],low[date[i]]); 98                           end 99                      else if fs[date[i]] then low[x]:=min(low[x],dfn[date[i]]);100       i:=next[i];101      end;102     if dfn[x]=low[x] then work(x);103   end;104 105  procedure built;   //染色后重新建图106  var i,j,k:longint;107   begin108     for k:=1 to 2*n do109      begin110        i:=head[k];111        while i<>0 do112         begin113           if (map[tr[k],tr[date[i]]]=false)and(tr[k]<>tr[date[i]]) then114            begin115             inc(rd[tr[date[i]]]);          //一个点的度116             map[tr[k],tr[date[i]]]:=true;117            end;118           i:=next[i];119         end;120      end;121   end;122  Procedure topo;         //拓扑排序123  var i,x:longint;124   begin125     le:=0;126     fillchar(fv,sizeof(fv),true);127     for i:=1 to lt do128      begin129       if rd[i]=0 then begin inc(le);stack[le]:=i;fv[i]:=false;end;130      end;131     x:=0;132     while x
          
           x)and(fv[i]) then recall(i);156 end;157 Procedure main;158 var i,j,k,l:longint;159 begin160 fillchar(fv,sizeof(fv),true);161 fillchar(fs,sizeof(fs),false);162 for i:=le downto 1 do //按拓扑序从后往前取点163 if fv[stack[i]] then164 begin165 fv[stack[i]]:=false;166 for j:=1 to 2*n do167 if tr[j]=stack[i] then 168 begin169 fs[j]:=true;170 if j>n then begin if fv[tr[j-n]] then recall(tr[j-n]);end //取一个点后应删除与他对立的点以及指向与他对立的点的点171 else begin if fv[tr[j+n]] then recall(tr[j+n]);end;172 173 end;174 end;175 for j:=1 to n do176 begin177 if fs[j] then178 begin179 print(si[j] div 60,si[j] mod 60);180 print((si[j]+d[j])div 60,(si[j]+d[j])mod 60);181 end;182 if fs[j+n] then183 begin184 print((ti[j]-d[j])div 60,(ti[j]-d[j]) mod 60);185 print(ti[j] div 60,ti[j] mod 60);186 end;187 writeln;188 end;189 end;190 191 Begin192 init;193 fillchar(fv,sizeof(fv),true);194 fillchar(fs,sizeof(fs),false);195 le:=0;196 for i:=1 to 2*n do197 if fv[i] then tarjan(i);198 writeln('YES');199 built;200 topo;201 main;202 end.