{"problem":{"name":"G. Gear Up","description":{"content":"_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,","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":6000,"memory_limit":131072},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10225G"},"statements":[{"statement_type":"Markdown","content":"_constroy_ has some gears, whose radii may vary. Two gears may be adjacent due to one of the following conditions:\n\nHe 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.\n\nNow, _constroy_ assigns an angular velocity to one of these gears, and then he wants to know the largest angular velocity among them.\n\nBut _sd0061_ thinks it is too easy for you, so he decides to replace some gears and then ask you the question.\n\nThe input contains multiple (about $30$) test cases.\n\nFor 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.\n\nThe 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.\n\nEach 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.\n\nThe 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:\n\nNote that the gears are always at rest.\n\nFor each test case, firstly, output \"_Case #x:_\" in one line (without quotes), where $x$ indicates the case number starting from $1$.\n\nThen, 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.\n\n## Input\n\nThe 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.\n\n## Output\n\nFor 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.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of grades and queries, respectively.  \nLet $ 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 $.  \n\n**Constraints**  \n1. $ 1 \\le n, q \\le 10^5 $  \n2. For each $ i \\in \\{1, \\dots, n\\} $: $ 0 \\le g_i \\le 10 $  \n3. For each query:  \n   - If type $ t = 1 $: $ 1 \\le l \\le r \\le n $  \n   - If type $ t = 2 $: $ 1 \\le i \\le n $, $ 0 \\le v \\le 10 $  \n\n**Objective**  \nFor each query of type $ t = 1 $ with range $ [l, r] $, compute:  \n$$\nf(l, r) = \\left( \\sum_{i=l}^{r} g_i \\right) - \\max_{i \\in [l,r]} g_i - \\min_{i \\in [l,r]} g_i\n$$  \nFor each query of type $ t = 2 $ with parameters $ (i, v) $, update:  \n$$\ng_i \\leftarrow v\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10225G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}