Problem H. Hierarchical layout

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

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.199s 0.010s 9