|Input file:||input.txt||Time limit:||1 sec|
|Output file:||output.txt||Memory limit:||256 Mb|
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:
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 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 must contain N integers Li — lengths of controls in order corresponding to input (Ai ≤ Li ≤ Bi).
If there is more than one solution, output any of them. If there is no solution, output a single integer −1.
1 ≤ N ≤ 1000; 1 ≤ Ai ≤ Bi ≤ 106;
0 ≤ Ci < N; C1 + C2 + ⋯ + CN = N − 1
|No.||Input file (
||Output file (|