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

---

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