G. Can Bash Save the Day?

[{"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$, $a_1, a_2, \dots, a_n$, $\\oplus$）均原样保留； - “bitwise exclusive OR” 译为 “按位异或”，但原文中使用的是符号 $\\oplus$，因此保留符号并说明为“bitwise exclusive OR”； - “test case” 在此题中未出现，但“query”统一译为“查询”； - “sequence” 译为“序列”； - “alternating sum” 未在题面中出现，无需处理； - 所有 Typst 下划线强调（如 `_1 1 5 4_`）原样保留； - 保留原文换行与段落结构； - 输出为严格合法 JSON 数组，字段名未改动。

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ denote the number of nodes and queries, respectively. Let $ A = (a_1, a_2, \dots, a_n) $ be a permutation of $ \{1, 2, \dots, n\} $. Let $ 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}^+ $. Let $ \text{dist}(u, v) $ denote the sum of edge weights along the unique path between nodes $ u $ and $ v $ in $ T $. Let $ \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. **Constraints** 1. $ 1 \leq n \leq 2 \cdot 10^5 $, $ 1 \leq q \leq 2 \cdot 10^5 $ 2. $ 1 \leq w(u,v) \leq 10^6 $ for all edges 3. For each query: - 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) $ - Type 2: Given $ x, y \in \{1, \dots, n\} $, swap $ a_x $ and $ a_y $: $ a_x \leftrightarrow a_y $ **Objective** For each query of type 1, output $ \text{ans}_i $. For each query of type 2, update the permutation $ A $ and set $ \text{ans}_i = \text{ans}_{i-1} $.