409889: GYM103828 B Too simple for a hard problem?

You will be given an array $$$a$$$, a weighted tree, and some queries. To make things a lot simpler, the array $$$a$$$ will just be a permutation.

The queries are very simple:

"$$$1$$$ $$$l$$$ $$$r$$$": Reverse $$$a[l \dots r]$$$. $$$(r - l + 1 \le 30)$$$

"$$$2$$$ $$$v$$$ $$$k$$$": $$$v$$$ is a node in the tree. You will be given $$$k$$$ (not necessarily disjoint) ranges, the $$$i$$$-th $$$(1 \le i \le k)$$$ range is $$$[l_i, r_i]$$$. You have to calculate: $$$$$$OR_{i = 1}^{k}\sum_{j = l_i}^{r_i}dist(a_j, v)$$$$$$ Where $$$OR$$$ is bitwise OR and $$$dist(u, v)$$$ is the distance between $$$u$$$ and $$$v$$$ in the tree (i.e. the sum of weights of the edges on the simple path between $$$u$$$ and $$$v$$$).

In the first line of the input, you will be given an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of testcases.

The first line of each testcase will contain two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 10^5)$$$ — the number of nodes in the tree, and the number of queries, respectively.

In the next line there will be $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$. It is guaranteed that the array $$$a$$$ is a permutation.

The next $$$n - 1$$$ lines will contain the edges of the tree. Each line will contain three integers $$$u$$$, $$$v$$$ $$$(1 \le u, v \le n)$$$ and $$$w$$$ $$$(0 \le w \le 10^3)$$$, which represents the endpoints and the weight of the edge, respectively. It is guaranteed that the given edges form a tree.

The next $$$q$$$ lines will contain the description of the queries.

You will be given the queries in an encoded format. Let $$$prevAns$$$ be $$$0$$$ initially.

For queries of the type $$$1$$$, you will be given three integers on a single line. $$$type$$$, $$$l$$$, and $$$r$$$. Where $$$type$$$ will be equal to $$$1$$$ for queries of this type, and $$$(1 \le l \le r \le n,$$$ $$$r - l + 1 \le 30)$$$.

For queries of the type $$$2$$$, on the first line of the query, you will be given three integers $$$type$$$, $$$v'$$$, and $$$k$$$. Where $$$type$$$ will be equal to $$$2$$$ for queries of this type, and $$$(1 \le v' \le n,$$$ $$$1 \le k \le 10^5)$$$. Then, the real value of $$$v$$$ will be $$$$$$v = (((v' \oplus prevAns) \cdot v') \mod n) + 1$$$$$$ Then follows $$$k$$$ lines, each containing two integers $$$l'$$$ and $$$r'$$$ $$$(1 \le l' \le r' \le n)$$$. Then, the real values of $$$l$$$ and $$$r$$$ will be $$$$$$l = (((l' \oplus prevAns) \cdot l') \mod n) + 1$$$$$$ $$$$$$r = (((r' \oplus prevAns) \cdot r') \mod n) + 1$$$$$$ (where $$$\oplus$$$ is bitwise Exclusive OR).

If $$$r < l$$$, then swap them.

Then update the value of $$$prevAns$$$ to be equal to the answer to this query.

It is guaranteed that the sum of $$$n$$$ over all testcases will not exceed $$$10^5$$$, the sum of $$$q$$$ over all testcases will not exceed $$$10^5$$$, the sum of $$$k$$$ over all the queries of the type $$$2$$$ in the entire input file will not exceed $$$10^5$$$.

For each query of the type $$$2$$$, output a line containing a single integer, the answer to that query.

2
1 1
1
2 1 2
1 1
1 1
2 3
2 1
1 2 24
2 1 2
1 1
2 2
1 1 2
2 2 3
1 1
2 2
1 2

0
24
24

Explanation of the second testcase from the sample:

In the first query, $$$v$$$ is node $$$1$$$, and the ranges are $$$[1, 1]$$$ and $$$[2, 2]$$$, The answer is $$$24$$$ $$$OR$$$ $$$0$$$ $$$=$$$ $$$24$$$.

$$$prevAns$$$ is now $$$24$$$.

After the second query, the array becomes $$$[1, 2]$$$.

In the last query, $$$v$$$ is node $$$(((2 \oplus 24) \cdot 2) \mod 2) + 1 = 1$$$, and the ranges are $$$[2, 2]$$$, $$$[1,1]$$$, and $$$[1,2]$$$. The answer is $$$24$$$ $$$OR$$$ $$$0$$$ $$$OR$$$ $$$(0 + 24)$$$ $$$=$$$ $$$24$$$.