{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou are given a tree with $n$ nodes labelled from $1$ to $n$, the root of which is the node labelled $1$.Every node in the tree will be endowed with values related to given parameters $a_1,a_2,\\cdots,a_n$, and each edge in the tree is endowed with a given bitwise operator which is one of the bitwise OR \u003ccode\u003e|\u003c/code\u003e, the bitwise AND \u003ccode\u003e\u0026amp;\u003c/code\u003e and the bitwise XOR \u003ccode\u003e^\u003c/code\u003e.\u003c/p\u003e\n\u003cp\u003eFor any pair of nodes $(u,v)$ indicating the $u$-th and the $v$-th node in the tree, the shortest path connecting them in the tree, denoted by$$\\displaystyle u\u003dp_0, p_1, p_2, \\cdots, p_{s-1}, p_s\u003dv$$together with operators along the path provide a value associated with $(u,v)$ given by$$\\displaystyle ((a_{p_0}\\ opt_1\\ a_{p_1})\\ opt_2\\ a_{p_2})\\cdots opt_s\\ a_{p_s})$$where $opt_i$ is the operator on the edge between the node $p_{i-1}$ and the node $p_i$ in this path.\u003c/p\u003e\n\u003cp\u003eNow you are given $q$ queries, each of which contains two integers $d$ and $u~(1\\le u\\le n)$.For this query, the value of the $i$-th node will be set to be $(a_i+i\\times d)$, and you are asked to calculate the bitwise OR, AND and XOR sum respectively of values for all the pairs $(u,v)$ where the $u$-th node is an ancestor of the $v$-th node. Note that a node is not considered as an ancestor of itself.\u003c/p\u003e\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003eThe first line contains two integers $n~(2 \\le n \\le 10^5)$ and $q~(1\\le q\\le 10^5)$ indicating the size of the tree and the number of queries.\u003c/p\u003e\n\u003cp\u003eThe second line contains $n$ integers $a_1,a_2,\\cdots,a_n~(1 \\le a_i \\le 10^{18})$ descirbed as above.\u003c/p\u003e\n\u003cp\u003eThe following $n-1$ lines describe the tree.The $i$-th line of them contains two integers $f~(1 \\le f \\le n)$ and $s~(0 \\le s \\le 2)$ which describe that the $f$-th node is the parent node of the $(i+1)$-th node, and the edge connecting the $(i+1)$-th node and the $f$-th node is endowed with a bitwise operator: if $s\u003d0$ the operator is \u003ccode\u003e|\u003c/code\u003e; if $s\u003d1$ the operator is \u003ccode\u003e\u0026amp;\u003c/code\u003e; and if $s\u003d2$ the operator is \u003ccode\u003e^\u003c/code\u003e.\u003c/p\u003e\n\u003cp\u003eEach of the following $q$ lines contains two integers $d~(0\\le d\\le 100)$ and $u~(1\\le u\\le n)$ describing a query.It is guaranteed that the node $u$ is not a leaf in the tree.\u003c/p\u003e\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eOutput $q$ lines corresponding to $q$ given queries, the $i$-th of which contains three integers representing the bitwise OR sum, the bitwise AND sum and the bitwise XOR sum for the $i$-th query respectively.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 4\n1 2 3 4 5\n1 0\n1 1\n2 0\n2 1\n0 1\n0 2\n1 2\n2 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7 1 4\n6 0 6\n12 0 12\n14 6 8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003eIn the sample case, the tree looks like\u003cimg src\u003d\"https://res.jisuanke.com/img/upload/20191114/2e1c35a3e7c4f33bb35966a1433773693552db44.png\" alt\u003d\"\"\u003e\u003c/p\u003e\u003cp\u003eFor the first query, the bitwise OR sum is $(1|2)~|~((1|2)|4)~|~((1|2)\\\u0026amp;5)~|~(1\\\u0026amp;3)~\u003d~7$.\u003c/p\u003e\u003cp\u003eFor the second query, the bitwise OR sum is $(2|4)~|~(2\\\u0026amp;5)~\u003d~6$.\u003c/p\u003e"}}]}