Gear Up

constroy has some gears, each with a radius. Two gears are considered adjacent if they meet one of the following conditions:

1. They share a common edge (i.e. they have equal linear velocity).

2. They share a common shaft (i.e. they have equal angular velocity).

It is guaranteed that no pair of gears meets both of the above conditions.

A series of continuous adjacent gears constitutes a gear path. There is at most one gear path between each two gears.

Now constroy assigns an angular velocity to one of these gears and then asks you to determine the largest angular velocity among them.

sd0061 thinks this problem is too easy, so he replaces some gears and then asks you the question again.

There are multiple test cases (about $30$).

For each test case:

The first line contains three integers $n, m, q$, the number of gears, the number of adjacent pairs and the number of operations. $(0 \leq m < n \leq 10^5, 0 \leq q \leq 10^5)$

The second line contains $n$ integers, of which the $i$-th integer represents $r_i$, the radius of the $i$-th gear. $(r_i \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$

Each of the next $m$ lines contains three integers $a, x, y$, the $x$-th gear and the $y$-th gear are adjacent in the $a$-th condition. $(a \in \{1, 2\}, 1 \leq x, y \leq n, x \neq y)$

Each of the next $q$ line contains three integers $a, x, y$, an operation ruled in the following: $(a \in \{1, 2\}, 1 \leq x \leq n, y \in \{2^\lambda \mid 0 \leq \lambda \leq 30\})$

$a = 1$ means to replace the $x$-th gear with another one of radius $y$.

$a = 2$ means to assign angular velocity $y$ to the $x$-th gear and then determine the maximum angular velocity.

For each test case, firstly output "Case #$x$:" in one line (without quotes), where $x$ indicates the case number starting from $1$, and then for each operation of $a = 2$, output in one line a real number, the natural logarithm of the maximum angular velocity, with the precision of $3$ digits.

4 3 4
1 4 16 2
1 2 4
1 2 3
2 1 4
1 1 16
1 2 4
2 4 4
1 4 16
4 3 5
2 16 4 8
2 1 2
1 2 3
1 1 4
2 1 4
1 3 8
2 1 16
1 4 1
2 1 8

Case #1:
1.386
Case #2:
2.773
3.466
2.773

2017 Multi-University Training Contest - Team 1