Problem Description

Given a tree with $n$ nodes, each node has two weights $a_i, b_i$. Define $f(S)$ as the smallest connected subgraph that contains the node set $S$. Then there are $q$ operations, each of the following forms:

• Operation 1: Given $l, r, v$, let $S$ be the set formed by all numbers in $[l, r]$. For all $i \in f(S)$, add $v \times b_i$ to $a_i$.
• Operation 2: Given $x$, query the value of $a_x$.
• Operation 3: Given $x$, query the sum of $a$ values of all nodes on the path from $1$ to $x$.

All answers are taken modulo $2^{32}$.

The problem is strictly online.

Input Format

The first line contains two integers $n, q$, representing the size of the tree and the number of operations.

The second line contains $n$ integers, representing the array $a$.

The third line contains $n$ integers, representing the array $b$.

The next $n - 1$ lines each contain two integers $x, y$, representing an edge of the tree.

The next $q$ lines each start with an integer $op$. If $op = 1$, then three integers $l, r, v$ follow, representing Operation 1. If $op = 2$, then one integer $x$ follows, representing Operation 2. If $op = 3$, then one integer $x$ follows, representing Operation 3.

You need to XOR $l, r, v$ in Operation 1, $x$ in Operation 2, and $x$ in Operation 3 with the answer of the previous query operation $lasans$. In particular, if there is no query operation before this operation, then $lasans = 0$.

Output Format

For each Operation 2 and Operation 3, output one line with the result modulo $2^{32}$.

4 5
2 3 4 5 
5 3 2 1 
3 1
3 2
2 4
2 4
1 6 1 4
2 4
1 3 6 2
3 3

5
2
2

Hint

Constraints: for $100\%$ of the testdata, $1 \le n \le 8 \times 10^5$, $1 \le q \le 3 \times 10^5$, and $0 \le l, r, v, x, a_i, b_i < 2^{32}$.

It is guaranteed that after decryption, $l, r, v, x$ satisfy $1 \le l \le r \le n$, $0 \le v < 2^{32}$, and $1 \le x \le n$.

Let $cnt_1$ be the number of operations with $op = 1$, $cnt_2$ be the number of operations with $op = 2$, and $cnt_3$ be the number of operations with $op = 3$. It is guaranteed that $\max(cnt_1, cnt_2, cnt_3) \le 0.6q$.

Translated by ChatGPT 5