Problem H. Hierarchical layout ≡

• problems
 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 (Ai ≤ Li ≤ Bi).

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

Constraints

1 ≤ N ≤ 1000; 1 ≤ Ai ≤ Bi ≤ 106;

0 ≤ Ci < N; C1 + C2 + ⋯  + CN = N − 1

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.092s 0.011s 13