Cho một cây gồm \(N\) đỉnh. Mỗi đỉnh \(i\) trên cây được gán một giá trị nguyên không âm \(A_i\).
Một đường đi đơn giữa hai đỉnh \(u\) và \(v\) (\(u < v\)) được gọi là hợp lệ nếu phép toán thao tác bit XOR (\(\oplus\)) của trọng số hai đỉnh đầu mút bằng đúng giá trị lớn nhất nằm trên toàn bộ các đỉnh thuộc đường đi đó. Cụ thể, điều kiện là:

Yêu cầu: Hãy đếm số lượng cặp đỉnh \((u, v)\) hợp lệ trên cây.

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng đỉnh.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) phân tách nhau bởi dấu cách.
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh nối giữa đỉnh \(u\) và đỉnh \(v\) trên cây.
• \(1 \le N \le 10^5\)
• \(0 \le A_i < 2^{30}\)

Output

• In ra một số nguyên duy nhất là số lượng cặp đỉnh \((u, v)\) với \(u < v\) tạo thành một đường đi hợp lệ.

Example

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

3