C. Chat. Aviéntate un nombre bien tuneadísimo y de paso la soluc
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tony has just returned from an exchange program in Spain. Since he has not practiced competitive programming for a while, Alexis and Iván want to help him remember some topics about trees, so they give him the following problem.

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. Each node has a color, which can be either white or black, and a weight $$$w_u$$$.

Alexis and Iván give Tony $$$q$$$ operations. Each operation is one of the following types:

  1. Change the weight of a node.
  2. Change the color of every node in a subtree: white nodes become black, and black nodes become white.
  3. Find the maximum possible total weight obtained by choosing some white nodes.

For the third type of operation, Tony cannot choose two nodes if one of them is an ancestor of the other. In other words, if Tony chooses a node, he cannot choose any of its ancestors or descendants.

Help Tony process all the operations and answer every query of the third type.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$) — the number of nodes in the tree and the number of operations, respectively.

The second line contains $$$n$$$ integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1 \le w_u \le 10^9$$$) — the initial weight of each node.

The third line contains a string $$$s$$$ of length $$$n$$$, consisting only of characters W and B. If $$$s_u = W$$$, node $$$u$$$ is initially white; otherwise, it is initially black.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) — an edge of the tree.

Each of the next $$$q$$$ lines describes one operation in one of the following formats:

  • 1 u x ($$$1 \le u \le n$$$, $$$1 \le x \le 10^9$$$) — change the weight of node $$$u$$$ to $$$x$$$.
  • 2 u ($$$1 \le u \le n$$$) — invert the color of every node in the subtree of $$$u$$$.
  • 3 — output the maximum possible total weight of a valid subset of white nodes.
Output

For each operation of type 3, print a single integer — the maximum possible total weight of a subset of white nodes such that no selected node is an ancestor of another selected node.

Examples
Input
3 6
5 4 7
WBW
1 2
1 3
3
2 1
3
1 3 10
2 3
3
Output
7
4
14
Input
4 7
8 5 9 6
WWBW
1 2
2 3
3 4
3
2 2
3
1 1 12
3
2 1
3
Output
8
9
12
6
Input
6 7
20 6 7 10 4 9
WBWWWB
1 2
1 3
2 4
2 5
3 6
3
2 2
3
1 3 30
3
2 1
3
Output
21
20
36
23