D. Historic Memories
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Many decades have passed since the great war. Humans are not destined to live too long, so with the change of generations, even such events from the past are gradually forgotten.

You set out on a journey to visit the places where the team of heroes passed during their trip. The map of the continent is represented as a tree, meaning that there is a unique path between any two of the $$$n$$$ cities. Traveling along each edge of the tree takes exactly one year.

In addition, each city is characterized by the value $$$s_i$$$ — the level of memory of the events of those days. It is known that with each passing year, the level of memory in all cities decreases by $$$1$$$. Sometimes events of the following types occur:

  • "- $$$t_i$$$ $$$x_i$$$" — at the beginning of year $$$t_i$$$, someone erects or restores a monument to the heroes and organizes an annual celebration in honor of the heroes' victory in city $$$x_i$$$. Then, starting from this year inclusive, the memory in this city stops decreasing.
  • "+ $$$t_i$$$ $$$x_i$$$" — at the beginning of year $$$t_i$$$, a monument is destroyed or the celebration is canceled in city $$$x_i$$$. Then, starting from this year inclusive, the level of memory in this city begins to decrease annually by $$$1$$$ again.

The level of memory does not drop below $$$0$$$ and can never increase. It is guaranteed that events of type '+' can occur only if before that the last event that occurred in the same city was of type '-'. Similarly, an event of type '-' cannot follow another event of type '-' in the same city.

You are interested in questions of the form "if at the beginning of year $$$t'_i$$$ you set out on a journey from city $$$x'_i$$$, and no more changes of type '+' or '-' will occur in the cities, what is the maximum level of memory about the heroes can you encounter?". Find an answer for every such query.

Input

The first line of the input contains two integers $$$n$$$ and $$$q$$$ separated by a space — the number of cities on the continent and the number of queries ($$$1 \le n, q \le 10^5$$$).

The second line contains $$$n$$$ integers $$$s_i$$$ — the initial levels of memory in the cities at the beginning of year number $$$0$$$ ($$$0 \le s_i \le 10^9$$$).

The next $$$n - 1$$$ lines contain a description of the edges of the tree: the $$$i$$$-th line contains a pair of integers $$$u_i$$$ and $$$v_i$$$ — the numbers of cities connected by the $$$i$$$-th edge ($$$1 \le u_i, v_i \le n$$$). It is guaranteed that there is a unique path from any vertex to any other vertex.

The next $$$q$$$ lines contain a description of the queries. Each query begins with the symbol '-', '+', or '?'. In the first two cases, two integers $$$t_i$$$ and $$$x_i$$$ follow the symbol, which mean "stop ('-') or resume ('+') the process of decreasing the level of memory in city $$$x_i$$$, starting from year $$$t_i$$$ inclusive". Otherwise, two integers $$$t'_i$$$ and $$$x'_i$$$ follow the symbol, representing the query "what is the maximum level of memory that can be encountered by leaving city $$$x'_i$$$ at the beginning of year $$$t'_i$$$?" ($$$0 \le t_i, t'_i \le 10^9$$$; $$$1 \le x_i, x'_i \le n$$$).

The queries are listed in chronological order. It is guaranteed that queries of types '-' and '+' with the same city alternate, and the first in this sequence must be '-'.

Output

For each query of type '?', output the answer to it on a separate line. Note that when answering such a query, you should not take into account subsequent queries of types '-' and '+'.

Examples
Input
3 9
5 7 4
1 2
1 3
- 0 3
? 0 1
? 0 2
? 0 3
+ 3 3
- 4 1
? 5 1
? 5 2
? 5 3
Output
6
7
5
1
2
2
Input
5 9
5 7 4 0 0
1 2
1 3
3 4
3 5
- 0 3
? 0 1
? 0 2
? 0 3
+ 4 3
- 5 1
? 5 1
? 5 2
? 5 3
Output
6
7
5
2
2
3