+ محدودیت زمان: ۵ ثانیه
+ محدودیت حافظه: ۵۱۲ مگابایت
----------
We have a country with $n$ cities. The cities in this country are connected by $n - 1$ two-way roads. We know that from each city, we can reach any other city by traversing some roads, meaning the structure of this country is a tree.
The cities are numbered from $1$ to $n$. We know the population of city $i$ is $w_i$. The \textit{difference} between two cities is defined as the XOR of the populations of the cities along the path between the two cities (including the start and end). The \textit{value} of the country is the sum of the differences between every pair of distinct cities.
Calculating the initial value of the country is not a hard task for the mayor. Therefore, we ask you to design a dynamic system. You will receive $q$ queries.
In each query, the population of city $v$ changes to $x$. We want you to write a program that calculates the initial value of the country and the value of the country after each change.
# ورودی
The first line of input contains an integer $n$, representing the number of cities in the country.
$$1 \leq n\leq 10^5$$
The second line contains $n$ integers $w_1, w_2, \dots, w_n$, representing the initial population of each city.
$$0 \leq w_i \leq 10^8$$
Each of the next $n - 1$ lines contain two integers $u$ and $v$, representing a road between cities $u$ and $v$ in the country.
$$1 \leq u, v\leq n$$
The following line contains an integer $q$, representing the number of queries.
$$1 \leq q \leq 10^5$$
The next $q$ lines each contain two integers $v$ and $x$, representing an operation that changes the population $w_v$ of city $v$ to $x$. It is guarantied that the roads form a tree.
$$0 \leq x \leq 10^8$$
$$1 \leq v\leq n$$
# خروجی
The output consists of $q + 1$ lines, where each line contains an integer representing the current value of the country.
# مثالها
## ورودی نمونه ۱
```
5
10 11 8 3 17
1 2
1 3
2 4
2 5
3
4 16
1 5
5 5
````
## خروجی نمونه ۱
```
123
157
202
170
````