Author: | A. Klenin | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
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 (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|