Mobiles Alabama

Time limit1sMemory limit128 MB

Summary

Parse a nested mobile description and compute, for each bar, the tie point that balances the weights hanging from its two sides.

Level: Medium5 of 10
Topics: Tree, DFS, Implementation, Math
Solved: No attempts yet

Problem

Alabama Mobiles Inc. designs and manufactures mobiles — lightweight kinetic sculptures consisting of bars hanging from strings. From each end of a bar hangs a string supporting either a small decorative object or another, smaller mobile. A well-designed mobile must have the weights of all decorative items balanced, so that each bar naturally tends to hang horizontally.

A bar can be balanced even when the weights hanging from its two sides are not equal. The string must be tied to the bar so that it divides the bar into two lengths $L_1$ and $L_2$ such that

$L_1 \times W_1 = L_2 \times W_2$

where $W_1$ is the total weight hanging from the $L_1$ side of the bar and $W_2$ is the total weight hanging from the other side.

Given a design for a mobile, determine, for every bar, where its string must be tied.

Each mobile is described as a collection of bars and decorative objects: you are given the lengths of the bars, the weights of all objects, and how the bars and objects are connected. Assume the bars and connecting strings are so lightweight that their weight is negligible compared to the decorative objects. Every mobile has at least one bar.

Input

The input consists of a number of mobile design specifications. Each mobile design is given as a parenthesized expression built from two basic forms:

( D w ) describes a decorative object, where $w$ is a floating-point number giving the object's weight.
( B # L m1 m2 ) describes a bar:
- # is an integer that uniquely identifies the bar. These identifiers are assigned densely, so a mobile with $k$ bars uses the numbers $1, \dots, k$ . The order in which the identifiers appear within an expression is arbitrary.
- $L$ is a floating-point number giving the length of the bar.
- m1 and m2 are two parenthesized expressions describing the parts hanging from each end of the bar.

Wherever a single space is shown between the components of a form, the actual input may contain one or more spaces and/or line breaks. As an exception, on either side of a ( or ) the input may contain zero or more spaces and/or line breaks.

Every mobile contains at least one bar. The end of the input is indicated by a line containing only ().

Output

For each mobile specification, print one line for each bar, in order of the bar's identifying number. Each line has the form

Bar N must be tied L from one end.

where $N$ is the bar's identifying number and $L$ is the smaller of the two lengths $L_1$ and $L_2$ described above, printed to one decimal place.

Examples3

Example 1

Input

(B 2 4.0
  (D 1.0 )
  (B 1 2.0  (D 1.0 )  (D 2.0 )))
()

Expected output

Bar 1 must be tied 0.7 from one end.
Bar 2 must be tied 1.0 from one end.

Example 2

Input

(B 1 10.0 (D 5.0) (D 5.0))
()

Expected output

Bar 1 must be tied 5.0 from one end.

Example 3

Input

(B 1 6.0 (D 1.0) (D 2.0))
()

Expected output

Bar 1 must be tied 2.0 from one end.