<PREV Problem:
NEXT>
Solved by 25 users: dan, rvashegin, tourist, sanekf, WsemirZ, Cheryl, wInuX, lutyj, zloy_mipt, KZ, mazahaka, MIKseR, defrager, RAVEman, UdH-WiNGeR, topspin, EAA2008, Dest, fetetriste, s01A15, tttttt, LiuChenheng, JohnJones_001, mathematic, regmar.
UserDateAttemptTimeCMSC
RAVEman27 feb 2009C++1700.13564 
Dest10 jul 2010C++200.32613 
JohnJones_00118 sep 2012C++200.31648 
fetetriste14 jul 2010C++900.38660 
defrager27 feb 2009C++600.41670 
rvashegin12 feb 2008C++100.41731 
RAVEman27 feb 2009C++1600.12736 
dan08 dec 2007C++200.41737 
dan08 dec 2007C++300.41749 
UdH-WiNGeR28 feb 2009Java101.55905 
mathematic20 sep 2012C++1300.06945 
EAA200815 mar 2010C++100.08947 
Languages
C++
19
Kylix
3
Java
2
FPC
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Time Management (Refactoring)

Time limit = 5 second(s)

As it often happens in programmers life. If was found that program you wrote do the job, but not the one you _really_ wants it to do. Problem statement needs some corrections.

You've completely forgot that there are very important task which cannot be thrown out. For example, sleeping, eating, Institue exams, going out with your girlfriend.

Input

First line contains nubmer of tasks N, 1 < N < 50001. Each of next N lines contains two integer numbers from [0, 2000000000] --- beginning and ending of time frame (those are represented in minutes from some fixed moment in time). Third number is 0 (task can be excluded) or 1 (task is mandatory). Task's lengths are not less than 20 minutes.

Output

First line should contain integer nubmer K — maximum number of non-overlapping tasks. Next K lines should contain description of K chosen tasks. In each line: identifier of a task and shift of that task (integer nubmer from [-10,10]).

All important task should be chosen.

If it's not possible, output should be single line: "NO SOLUTION"

Input#1
4
30 66 1
1 30 0
6 38 0
20 52 0
Output#1
2
0 10
1 -10
Input#2
7
56 98 1
30 66 0
1 30 0
37 59 1
6 38 0
40 62 0
48 70 0
Output#2
3
0 10
3 7
2 -10
Input#3
7
56 98 0
30 66 0
1 30 0
37 58  1
6 38 1
40 62 1
48 70 0
Output#3
3
4 -10
3 -9
5 9
Input#4
3
0 21 1
20 44 0
10 41 1
Output#4
2
2 2
0 -9

Input#5
5
0 100 0
0 21 1
20 43 0
20 44 1
10 41 1
Output#5
NO SOLUTION


Author:
Artem Voroztsov, MIPT Personal programming contest, 7 October 2007, Translated by Mishik.
4 December 2007

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 34.204.176.125