محدودیت زمان: ۵ ثانیه
محدودیت حافظه: ۵۱۲ مگابایت

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

خروجی نمونه ۱

ارسال پاسخ برای این سؤال