Khoảng ba mươi năm trước, thanh niên Krešo tham gia lần đầu tiên vào cuộc thi tin học quốc gia. Tương tự như hôm nay, sự kiện khai mạc của cuộc thi bao gồm một loạt diễn giả cố gắng thể hiện tầm quan trọng của sự kiện này đối với các thí sinh thông qua những thông điệp truyền động lực. Khán giả, với sự nhiệt tình, bắt đầu vỗ tay mỗi vài giây một lần, nhưng Krešo đã bị khó chịu bởi một câu nói. Cụ thể, một trong những diễn giả tuyên bố ông ta đánh giá cao hơn phép toán logic ~AND~ hơn là phép toán ~OR~ vì, bất kể danh tính của người chiến thắng là ai, đối với ông ta cả Mirko và Slavko đều là người chiến thắng của cuộc thi quốc gia, thay vì người chiến thắng là Mirko hoặc Slavko. Krešo tức giận, đứng dậy và bắt đầu giải thích cho khán giả rằng đây là một phép toán được biết đến là phép toán ~XOR~ (phổ biến là ~XOR~). Sau khi đã phát biểu của mình, ông đưa nhiệm vụ tiếp theo cho diễn giả xuất sắc để xác minh hiểu biết của mình.

Có một cây cho trước gồm ~N~ nút, trong đó mỗi nút được gán một giá trị. Giá trị của một đường đi trên cây đó được xác định là phép toán ~XOR~ của tất cả các giá trị nút trên đường đi đó. Nhiệm vụ của bạn là xác định tổng các giá trị của tất cả các đường đi trên cây, bao gồm cả các đường đi chỉ chứa một nút.

Ba mươi năm sau, Krešo đã thuyết phục được các tác giả của các nhiệm vụ COCI để bao gồm nhiệm vụ này trong một trong các vòng thi. Hãy giúp chúng tôi trả lại niềm tin của Krešo vào tương lai của lập trình cạnh tranh.

Ghi chú

Phép toán ~XOR (⊕)~ là một phép toán nhị phân được áp dụng riêng lẻ trên mỗi cặp bit tương ứng của hai toán hạng của nó sao cho một số bit trong kết quả được đặt thành 1 nếu và chỉ nếu bit đó trong một toán hạng duy nhất được đặt thành 1.

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \leq N \leq 100,000)~ chỉ số nút trong cây.
• Dòng thứ hai chứa ~N~ số nguyên ~v_i~ ~(0 \leq v_i \leq 3,000,000)~ cách nhau bởi dấu cách, giá trị của nút thứ ~i~.
• Các dòng tiếp theo ~N-1~ chứa hai số ~a_j~ và ~b_j~ ~(1 \leq a_j, b_j \leq N)~ chỉ ra rằng có một cạnh giữa các nút ~a_j~ và ~b_j~.

Onput

In tổng các giá trị cần thiết cho tất cả các đường đi trên cây.

Chú ý

• ~30 \%~ tổng số điểm thỏa mãn ~N \leq 200~.
• ~50 \%~ tổng số điểm thỏa mãn ~N \leq 1000~.
• ~20 \%~ tổng số điểm thỏa mãn mỗi node ~x~ từ ~1~ đến ~N-1~ đều nối với node ~x+1~.

Sample Input 1

3
1 2 3
1 2
2 3

Sample Output 1

10

Sample Input 2

5
2 3 4 2 1
1 2
1 3
3 4
3 5

Sample Output 2

64

Sample Input 3

6
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6

Sample Output 3

85

Giải thích

Trong test thứ nhất:

• Giá trị của đường đi từ nút ~1~ đến nút ~1~ là ~1~
• Giá trị của đường đi từ nút ~1~ đến nút ~2~ là ~1 ⊕ 2 = 3~
• Giá trị của đường đi từ nút ~1~ đến nút ~3~ là ~1 ⊕ 2 ⊕ 3 = 0~
• Giá trị của đường đi từ nút ~2~ đến nút ~2~ là ~2~
• Giá trị của đường đi từ nút ~2~ đến nút ~3~ là ~2 ⊕ 3 = 1~
• Giá trị của đường đi từ nút ~3~ đến nút ~3~ là ~3~

Tổng của tất cả các đường đi là ~1 + 3 + 0 + 2 + 1 + 3 = 10~.