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