You may have heard the saying "money doesn't grow on trees." Obviously, whoever came up with it stunk at both botany and programming. You've learned that creating trees which grow obscene amounts of money is so trivial, that it's left as an exercise to the reader. Time for the real challenge: profiting off your invention!
You have rooted your money-tree at node $1$, and each node has a specified moola value. The amount of money that some subtree rooted at node $x$ will produce is equal to the product of the moola values of all nodes in $x$'s subtree. Initially, all nodes will have a moola value of 1.
Now, $q$ times, one of two things happen, given to you in the form of "t x y":
If $t = 1$, you give node $x$ a special fertilizer which sets its moola value to $y$.
If $t = 2$, a customer comes in and asks "how many times more valuable is subtree $x$ than subtree $y$"? Formally, what is the value of subtree $x$ divided by the value of subtree $y$. Also, you don't like printing massive numbers, so subtree $x$ is more than $10^9$ times greater than subtree $y$, only print "1000000000".
The first line will contain a single integer $n$, the number of nodes in the tree. $n -1$ lines follow, each containing two different integers, describing the edges of the tree. Additional constraint on input: these edges will form a tree.
After that there will be a single integer $q$: the number of queries. $q$ line follow, each of the form $t x y$, as described above.
$1 <= n, q <= 3 * 10^5$
$1 <= t <= 2$
$1 <= x, y <= n$
For each query of type 2, print a single line with one real number: how many times more valuable subtree $x$ is than subtree $y$. HOWEVER, if this value is >= $10^9$, then print just $1000000000$ instead.
Your answer will be accepted if your answers to all queries have absolute or relative error of at most $10^(-6)$.
## Input
The first line will contain a single integer $n$, the number of nodes in the tree. $n -1$ lines follow, each containing two different integers, describing the edges of the tree. Additional constraint on input: these edges will form a tree.After that there will be a single integer $q$: the number of queries. $q$ line follow, each of the form $t x y$, as described above.$1 <= n, q <= 3 * 10^5$$1 <= t <= 2$$1 <= x, y <= n$
## Output
For each query of type 2, print a single line with one real number: how many times more valuable subtree $x$ is than subtree $y$. HOWEVER, if this value is >= $10^9$, then print just $1000000000$ instead.Your answer will be accepted if your answers to all queries have absolute or relative error of at most $10^(-6)$.
[samples]
**Definitions**
Let $ T = (V, E) $ be a rooted tree with $ n $ nodes, where node $ 1 $ is the root.
Let $ w: V \to \mathbb{R}^+ $ be the weight function assigning moola values to nodes, initially $ w(v) = 1 $ for all $ v \in V $.
For a node $ x $, let $ S(x) \subseteq V $ denote the set of nodes in the subtree rooted at $ x $.
Define the subtree value:
$$
V(x) = \prod_{u \in S(x)} w(u)
$$
**Constraints**
1. $ 1 \le n, q \le 3 \cdot 10^5 $
2. For each query:
- If $ t = 1 $: update $ w(x) \leftarrow y $, where $ y \in \mathbb{R}^+ $
- If $ t = 2 $: compute $ \frac{V(x)}{V(y)} $, and output:
$$
\begin{cases}
\frac{V(x)}{V(y)} & \text{if } \frac{V(x)}{V(y)} < 10^9 \\
1000000000 & \text{otherwise}
\end{cases}
$$
**Objective**
Process $ q $ queries of type $ t \in \{1, 2\} $:
- Type 1: Update node weight.
- Type 2: Output the ratio $ \frac{V(x)}{V(y)} $, clamped at $ 10^9 $.