Processing math: 100%

Problem H. Hierarchical layout

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Young programmer Vasya was recruited by a "WorkMountain" software company. His first assignment was to implement an algorithm which would position a hierarchy of controls on a GUI form according to constraints specified by form designer.

Although Vasya was asked to position controls in two dimensions, he decided to solve one-dimensional problem first.

A control number i is represented by a segment of a line with minimum length Ai, maximum length Bi and has Ci children controls. Controls can be nested to arbitrary depth.

Constraints are simple:

  1. actual control length must be between minimum and maximum lengths, inclusive;
  2. for every control with one or more children, control length must be exactly equal to the sum of children lengths.

Your program must, given a control (possibly with children) and constraints, assign a length to every control so that every constraint is satisfied.

Input file format

Input file contains integer N — total number of controls, followed by a control description. Each control description contains integers Ai Bi Ci, followed by Ci descriptions of i-th control's children.

Output file format

Output file must contain N integers Li — lengths of controls in order corresponding to input (AiLiBi).

If there is more than one solution, output any of them. If there is no solution, output a single integer 1.

Constraints

1N1000; 1AiBi106;

0Ci<N; C1+C2++CN=N1

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
10 20 0
15
2
3
100 100 2
40 50 0
55 55 0
100 45 55
3
2
5 6 1
7 8 0
-1

0.063s 0.009s 13