Problem H. Hierarchical layout ≡

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 A_i, maximum length B_i and has C_i 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 A_i B_i C_i, followed by C_i descriptions of i-th control's children.

Output file format

Output file must contain N integers L_i — lengths of controls in order corresponding to input (A_i ≤ L_i ≤ B_i).

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 ≤ A_i ≤ B_i ≤ 10⁶;

0 ≤ C_i < N; C₁ + C₂ +  ⋯  + C_N = N − 1

Sample tests

1
10 20 0

15

3
100 100 2
40 50 0
55 55 0

100 45 55

2
5 6 1
7 8 0

-1