A telecom crew is calibrating a chain of signal relays scattered across a mountain range. The relays are numbered 0 to n - 1, and relay 0 is the reference tower whose broadcast frequency defines the baseline. The relays are wired into a tree: exactly n - 1 physical links connect them, so every relay is reachable from the reference tower through exactly one path. Each link joins two relays u and v and carries a calibration multiplier: whenever a signal travels from u to v along that link, its frequency is multiplied by p and divided by q. Travelling the other way, from v to u, does the opposite (multiplied by q, divided by p). For every relay, report the exact ratio between its calibrated frequency and the frequency of relay 0, written as a fraction in lowest terms. Because the tree can be deep and the multipliers can compound across many links, the numerator and denominator of an answer may be far too large to fit in a 64-bit integer — you must compute and print them exactly, using arbitrary-precision arithmetic, never floating point and never a modulus.

Input format

Line 1: a single integer n — the number of relays. Each of the next n - 1 lines contains four integers u v p q — a link between relay u and relay v (0-indexed, u != v). Travelling from u to v along that link multiplies the frequency by p and divides it by q; travelling from v to u does the opposite. The n - 1 links are guaranteed to connect all n relays into a single tree.

Output format

Print n lines. The i-th line (0-indexed) must contain two integers num den separated by a space: the numerator and denominator, in lowest terms (den > 0, gcd(num, den) = 1), of the exact ratio frequency(i) / frequency(0). For relay 0 itself this ratio is 1 1.

Constraints

• 2 <= n <= 60
• 0 <= u, v <= n - 1, u != v
• 1 <= p, q <= 10^9
• The given links form a tree on the n relays.

4
0 1 3 2
1 2 5 4
0 3 7 1

1 1
3 2
15 8
7 1

3
1 0 2 3
2 1 5 7

1 1
3 2
21 10