{"problem":{"name":"G. Can Bash Save the Day?","description":{"content":"Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a maste","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":786432},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF757G"},"statements":[{"statement_type":"Markdown","content":"Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a master in programming as well. He agrees to free the Pokemons if Bash can answer his questions.\n\nInitially, Meowth gives Bash a weighted tree containing _n_ nodes and a sequence _a_1, _a_2..., _a__n_ which is a permutation of 1, 2, ..., _n_. Now, Mewoth makes _q_ queries of one of the following forms:\n\n*   _1 l r v_: meaning Bash should report , where _dist_(_a_, _b_) is the length of the shortest path from node _a_ to node _b_ in the given tree.\n*   _2 x_: meaning Bash should swap _a__x_ and _a__x_ + 1 in the given sequence. This new sequence is used for later queries.\n\nHelp Bash to answer the questions!\n\n## Input\n\nThe first line contains two integers _n_ and _q_ (1 ≤ _n_ ≤ 2·105, 1 ≤ _q_ ≤ 2·105) — the number of nodes in the tree and the number of queries, respectively.\n\nThe next line contains _n_ space-separated integers — the sequence _a_1, _a_2, ..., _a__n_ which is a permutation of 1, 2, ..., _n_.\n\nEach of the next _n_ - 1 lines contain three space-separated integers _u_, _v_, and _w_ denoting that there exists an undirected edge between node _u_ and node _v_ of weight _w_, (1 ≤ _u_, _v_ ≤ _n_, _u_ ≠ _v_, 1 ≤ _w_ ≤ 106). It is guaranteed that the given graph is a tree.\n\nEach query consists of two lines. First line contains single integer _t_, indicating the type of the query. Next line contains the description of the query:\n\n*   **t = 1**: Second line contains three integers _a_, _b_ and _c_ (1 ≤ _a_, _b_, _c_ < 230) using which _l_, _r_ and _v_ can be generated using the formula given below:\n    *   ,\n    *   ,\n    *   .\n*   **t = 2**: Second line contains single integer _a_ (1 ≤ _a_ < 230) using which _x_ can be generated using the formula given below:\n    *   .\n\nThe _ans__i_ is the answer for the _i_\\-th query, assume that _ans_0 = 0. If the _i_\\-th query is of type 2 then _ans__i_ = _ans__i_ - 1. It is guaranteed that:\n\n*   **for each query of type 1**: 1 ≤ _l_ ≤ _r_ ≤ _n_, 1 ≤ _v_ ≤ _n_,\n*   **for each query of type 2**: 1 ≤ _x_ ≤ _n_ - 1.\n\nThe operation means bitwise exclusive OR.\n\n## Output\n\nFor each query of type 1, output a single integer in a separate line, denoting the answer to the query.\n\n[samples]\n\n## Note\n\nIn the sample, the actual queries are the following:\n\n*   _1 1 5 4_\n*   _1 1 3 3_\n*   _2 3_\n*   _2 2_\n*   _1 1 3 3_","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"Whoa! You did a great job helping Team Rocket who managed to capture all the Pokemons sent by Bash. Meowth, part of Team Rocket, having already mastered the human language, now wants to become a master in programming as well. He agrees to free the Pokemons if Bash can answer his questions.\\n\\nInitially, Meowth gives Bash a weighted tree containing $n$ nodes and a sequence $a_1, a_2, ..., a_n$ which is a permutation of $1, 2, ..., n$. Now, Meowth makes $q$ queries of one of the following forms:\\n\\nHelp Bash to answer the questions!\\n\\nThe first line contains two integers $n$ and $q$ ($1 ≤ n ≤ 2·10^5$, $1 ≤ q ≤ 2·10^5$) — the number of nodes in the tree and the number of queries, respectively.\\n\\nThe next line contains $n$ space-separated integers — the sequence $a_1, a_2, ..., a_n$ which is a permutation of $1, 2, ..., n$.\\n\\nEach of the next $n - 1$ lines contain three space-separated integers $u$, $v$, and $w$ denoting that there exists an undirected edge between node $u$ and node $v$ of weight $w$, ($1 ≤ u, v ≤ n$, $u ≠ v$, $1 ≤ w ≤ 10^6$). It is guaranteed that the given graph is a tree.\\n\\nEach query consists of two lines. First line contains single integer $t$, indicating the type of the query. Next line contains the description of the query: \\n\\nThe $ans_i$ is the answer for the $i$-th query, assume that $ans_0 = 0$. If the $i$-th query is of type 2 then $ans_i = ans_{i - 1}$. It is guaranteed that: \\n\\nThe $\\\\oplus$ operation means bitwise exclusive OR.\\n\\nFor each query of type $1$, output a single integer in a separate line, denoting the answer to the query.\\n\\nIn the sample, the actual queries are the following: \\n\\n\"},{\"iden\":\"input\",\"content\":\"The first line contains two integers $n$ and $q$ ($1 ≤ n ≤ 2·10^5$, $1 ≤ q ≤ 2·10^5$) — the number of nodes in the tree and the number of queries, respectively. The next line contains $n$ space-separated integers — the sequence $a_1, a_2, ..., a_n$ which is a permutation of $1, 2, ..., n$. Each of the next $n - 1$ lines contain three space-separated integers $u$, $v$, and $w$ denoting that there exists an undirected edge between node $u$ and node $v$ of weight $w$, ($1 ≤ u, v ≤ n$, $u ≠ v$, $1 ≤ w ≤ 10^6$). It is guaranteed that the given graph is a tree. Each query consists of two lines. First line contains single integer $t$, indicating the type of the query. Next line contains the description of the query: \\n\\n*t = 1*: Second line contains three integers $a$, $b$ and $c$ ($1 ≤ a, b, c < 2^{30}$) using which $l$, $r$ and $v$ can be generated using the formula given below:\\n\\n$l = (a \\\\oplus ans_{i-1}) \\\\bmod n + 1$,  $r = (b \\\\oplus ans_{i-1}) \\\\bmod n + 1$,  $v = (c \\\\oplus ans_{i-1}) \\\\bmod n + 1$.\\n\\n*t = 2*: Second line contains single integer $a$ ($1 ≤ a < 2^{30}$) using which $x$ can be generated using the formula given below:\\n\\n$x = (a \\\\oplus ans_{i-1}) \\\\bmod (n - 1) + 1$.\\n\\nThe $ans_i$ is the answer for the $i$-th query, assume that $ans_0 = 0$. If the $i$-th query is of type 2 then $ans_i = ans_{i - 1}$. It is guaranteed that: \\n\\n*for each query of type 1*: $1 ≤ l ≤ r ≤ n$, $1 ≤ v ≤ n$, \\n*for each query of type 2*: $1 ≤ x ≤ n - 1$. The $\\\\oplus$ operation means bitwise exclusive OR.\"},{\"iden\":\"output\",\"content\":\"For each query of type $1$, output a single integer in a separate line, denoting the answer to the query.\"},{\"iden\":\"note\",\"content\":\"In the sample, the actual queries are the following: \\n\\n_1 1 5 4_\\n_1 1 3 3_\\n_2 3_\\n_2 2_\\n_1 1 3 3_ \"}]\n\n### 说明：\n- 所有数学公式（如 $n$, $a_1, a_2, \\dots, a_n$, $\\\\oplus$）均原样保留；\n- “bitwise exclusive OR” 译为 “按位异或”，但原文中使用的是符号 $\\\\oplus$，因此保留符号并说明为“bitwise exclusive OR”；\n- “test case” 在此题中未出现，但“query”统一译为“查询”；\n- “sequence” 译为“序列”；\n- “alternating sum” 未在题面中出现，无需处理；\n- 所有 Typst 下划线强调（如 `_1 1 5 4_`）原样保留；\n- 保留原文换行与段落结构；\n- 输出为严格合法 JSON 数组，字段名未改动。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of nodes and queries, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \nLet $ T = (V, E) $ be a weighted tree with $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E $, where each edge $ (u, v) \\in E $ has weight $ w(u,v) \\in \\mathbb{Z}^+ $.  \nLet $ \\text{dist}(u, v) $ denote the sum of edge weights along the unique path between nodes $ u $ and $ v $ in $ T $.  \nLet $ \\text{ans}_0 = 0 $, and for $ i \\geq 1 $, let $ \\text{ans}_i $ be the answer to the $ i $-th query, with $ \\text{ans}_i = \\text{ans}_{i-1} $ for type-2 queries.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ 1 \\leq q \\leq 2 \\cdot 10^5 $  \n2. $ 1 \\leq w(u,v) \\leq 10^6 $ for all edges  \n3. For each query:  \n   - Type 1: Given $ x \\in \\{1, \\dots, n\\} $, compute $ \\text{ans}_i = \\text{ans}_{i-1} \\oplus \\left( \\sum_{j=1}^n \\text{dist}(x, j) \\cdot a_j \\right) $  \n   - Type 2: Given $ x, y \\in \\{1, \\dots, n\\} $, swap $ a_x $ and $ a_y $: $ a_x \\leftrightarrow a_y $  \n\n**Objective**  \nFor each query of type 1, output $ \\text{ans}_i $.  \nFor each query of type 2, update the permutation $ A $ and set $ \\text{ans}_i = \\text{ans}_{i-1} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF757G","tags":["data structures","divide and conquer","graphs","trees"],"sample_group":[["5 5\n4 5 1 3 2\n4 2 4\n1 3 9\n4 1 4\n4 5 2\n1\n1 5 4\n1\n22 20 20\n2\n38\n2\n39\n1\n36 38 38","23\n37\n28"]],"created_at":"2026-03-03 11:00:39"}}