_constroy_ has some gears, whose radii may vary. Two gears may be adjacent due to one of the following conditions:
He guarantees that there are no two gears that satisfy both of the above conditions, and there is at most one transmission path between every two gears, where a transmission path is a sequence of different gears, in which two consecutive gears are adjacent.
Now, _constroy_ assigns an angular velocity to one of these gears, and then he wants to know the largest angular velocity among them.
But _sd0061_ thinks it is too easy for you, so he decides to replace some gears and then ask you the question.
The input contains multiple (about $30$) test cases.
For each test case, the first line contains three integers $n$, $m$, $q$ ($0 <= n, m, q <= 10^5$, $m < n$), indicating the number of gears, the number of adjacent pairs and the number of operations respectively.
The second line contains $n$ integers, the $i$-th number of which is $r_i$ ($r_i in lbrace 2^0, 2^1, \\dots, 2^(30) rbrace$), denoting the radius of the $i$-th gear.
Each of the next $m$ lines contains three integers $a$, $x$, $y$ ($a in lbrace 1, 2 rbrace$, $1 <= x, y <= n$, $x eq.not y$), representing that the $x$-th gear and the $y$-th one are adjacent due to the $a$-th condition.
The next $q$ lines describe the operations in chronological order. Each line contains three integers $a$, $x$, $y$ ($a in lbrace 1, 2 rbrace$, $1 <= x <= n$, $y in lbrace 2^0, 2^1, \\dots, 2^(30) rbrace$), representing an operation where:
Note that the gears are always at rest.
For each test case, firstly, output "_Case #x:_" in one line (without quotes), where $x$ indicates the case number starting from $1$.
Then, for each operation with $a = 2$, output a real number in one line, denoting the natural logarithm of the maximum angular velocity, with the precision for exactly three digits after the decimal point.
## Input
The input contains multiple (about $30$) test cases.For each test case, the first line contains three integers $n$, $m$, $q$ ($0 <= n, m, q <= 10^5$, $m < n$), indicating the number of gears, the number of adjacent pairs and the number of operations respectively.The second line contains $n$ integers, the $i$-th number of which is $r_i$ ($r_i in lbrace 2^0, 2^1, \\dots, 2^(30) rbrace$), denoting the radius of the $i$-th gear.Each of the next $m$ lines contains three integers $a$, $x$, $y$ ($a in lbrace 1, 2 rbrace$, $1 <= x, y <= n$, $x eq.not y$), representing that the $x$-th gear and the $y$-th one are adjacent due to the $a$-th condition.The next $q$ lines describe the operations in chronological order. Each line contains three integers $a$, $x$, $y$ ($a in lbrace 1, 2 rbrace$, $1 <= x <= n$, $y in lbrace 2^0, 2^1, \\dots, 2^(30) rbrace$), representing an operation where: if $a = 1$, the operation is to replace the $x$-th gear with another one of radius $y$; if $a = 2$, the operation is to ask you to determine the maximum possible angular velocity among all the gears if _constroy_ assigns an angular velocity of $y$ to the $x$-th gear. Note that the gears are always at rest.
## Output
For each test case, firstly, output "_Case #x:_" in one line (without quotes), where $x$ indicates the case number starting from $1$.Then, for each operation with $a = 2$, output a real number in one line, denoting the natural logarithm of the maximum angular velocity, with the precision for exactly three digits after the decimal point.
[samples]
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the number of grades and queries, respectively.
Let $ G = (g_1, g_2, \dots, g_n) $ be a sequence of grades, where $ g_i \in \mathbb{Z} $ and $ 0 \le g_i \le 10 $.
**Constraints**
1. $ 1 \le n, q \le 10^5 $
2. For each $ i \in \{1, \dots, n\} $: $ 0 \le g_i \le 10 $
3. For each query:
- If type $ t = 1 $: $ 1 \le l \le r \le n $
- If type $ t = 2 $: $ 1 \le i \le n $, $ 0 \le v \le 10 $
**Objective**
For each query of type $ t = 1 $ with range $ [l, r] $, compute:
$$
f(l, r) = \left( \sum_{i=l}^{r} g_i \right) - \max_{i \in [l,r]} g_i - \min_{i \in [l,r]} g_i
$$
For each query of type $ t = 2 $ with parameters $ (i, v) $, update:
$$
g_i \leftarrow v
$$