G. Gear Up
time limit per test
6 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

constroy has some gears, whose radii may vary. Two gears may be adjacent due to one of the following conditions:

  • they mesh together, which causes them to have equal linear velocity on edge; or
  • they are fixed on the same shaft, which causes them to have equal angular velocity.

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.

Input

The input contains multiple (about $$$30$$$) test cases.

For each test case, the first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$0 \leq n, m, q \leq 10^5$$$, $$$m \lt 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}, \ldots, 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 \leq x, y \leq n$$$, $$$x \neq 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 \leq x \leq n$$$, $$$y \in \lbrace 2^{0}, 2^{1}, \ldots, 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.

Example
Input
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
Output
Case #1:
1.386
Case #2:
2.773
3.466
2.773