<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.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 = 54.224.164.166