{"raw_statement":[{"iden":"problem statement","content":"You are given an undirected graph $G$ with $2^N + 1$ vertices and $2^{N+1} - 1$ edges. The vertices are numbered $0, 1, \\dots, 2^N$, and the edges are numbered $1, 2, \\dots, 2^{N+1}-1$.\nEach edge in $G$ belongs to one of $N+1$ types, ranging from type $0$ to type $N$.  \nFor type $i$ $(0 \\le i \\le N)$, there are exactly $2^i$ edges, which are numbered $2^i+0, 2^i+1, \\dots, 2^i+(2^i-1)$. The edge numbered $2^i + j$ $(0 \\leq j \\leq 2^i - 1)$ is an undirected edge of length $C_{2^i + j}$ that connects vertex $j \\times 2^{N-i}$ and vertex $(j+1) \\times 2^{N-i}$.\nFor example, when $N = 3$, $G$ looks like the following graph:\n![image](https://img.atcoder.jp/ttpc2024_1/3e862a8815475973ce0762481400dfd3.png)\nYou are given $Q$ queries to process. There are two types of queries:\n\n*   `1 j x`: Change the length of edge $j$ to $x$.\n*   `2 s t`: Find the shortest path length from vertex $s$ to vertex $t$."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1 \\le N \\le 18$\n*   $1 \\le C_j \\le 10^7$ $(1 \\le j \\le 2^{N+1}-1)$\n*   $1 \\le Q \\le 2 \\times 10^5$\n*   In the query `1 j x`, $1 \\le j \\le 2^{N+1}-1$ and $1 \\le x \\le 10^7$.\n*   In the query `2 s t`, $0 \\le s < t \\le 2^N$.\n*   There is at least one `2 s t` query."},{"iden":"partial score","content":"$30$ points will be awarded for passing the testset satisfying the additional constraint: There is no `1 j x` query."},{"iden":"input","content":"The input is given in the following format. Note that vertex numbering starts from $0$, while edge numbering starts from $1$.\n\n$N$\n$C_1$ $C_2$ $\\cdots$ $C_{2^{N+1}-1}$\n$Q$\n$\\text{query}_1$\n$\\text{query}_2$\n$\\vdots$\n$\\text{query}_Q$\n\nHere, $\\text{query}_i$ represents the $i$\\-th query. Each query is given in one of the following formats:\n\n1 $j$ $x$\n\n2 $s$ $t$"},{"iden":"sample input 1","content":"3\n7 1 14 3 9 4 8 2 6 5 5 13 8 2 3\n10\n2 0 1\n2 0 4\n2 4 6\n2 4 8\n2 3 5\n1 6 30\n2 3 5\n2 4 6\n1 1 10000000\n2 0 8"},{"iden":"sample output 1","content":"2\n1\n4\n8\n17\n18\n13\n15\n\n*   In the 1st query, using edge $8$, the path $0 \\to 1$ results in a total distance of $2$.\n*   In the 2nd query, using edge $2$, the path $0 \\to 4$ results in a total distance of $1$.\n*   In the 3rd query, using edge $6$, the path $4 \\to 6$ results in a total distance of $4$.\n*   In the 4th query, using edges $2, 1$, the path $4 \\to 0 \\to 8$ results in a total distance of $8$.\n*   In the 5th query, using edges $11, 6, 13$, the path $3 \\to 4 \\to 6 \\to 5$ results in a total distance of $17$.\n*   In the 6th query, the length of edge $6$ is updated from $4$ to $30$.\n*   In the 7th query, using edges $11, 12$, the path $3 \\to 4 \\to 5$ results in a total distance of $18$.\n*   In the 8th query, using edges $2, 1, 15, 14$, the path $4 \\to 0 \\to 8 \\to 7 \\to 6$ results in a total distance of $13$.\n*   In the 9th query, the length of edge $1$ is updated from $7$ to $10000000$.\n*   In the 10th query, using edges $2, 3$, the path $0 \\to 4 \\to 8$ results in a total distance of $15$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}